exotic-list-monads 1.0.0 → 1.0.1

raw patch · 5 files changed

+102/−57 lines, 5 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• README.md +1/−7
• exotic-list-monads.cabal +2/−2
• src/Control/Monad/List/Exotic.hs +25/−19
• src/Control/Monad/List/NonEmpty/Exotic.hs +70/−29

@@ -1,5 +1,9 @@ # exotic-list-monad changelog +## v1.0.1++- Fixes in documentation+ ## v1.0.0  - Initial version

@@ -1,13 +1,7 @@ # exotic-list-monads -[![Build Status](https://api.travis-ci.com/maciejpirog/exotic-list-monads.png?branch=master)](http://travis-ci.com/maciejpirog/exotic-list-monads)--A Haskell library that defines a few non-standard monads on lists and non-empty lists --## Description- The usual [list monad](https://hackage.haskell.org/package/base-4.14.0.0/docs/src/GHC.Base.html#line-1133) is only one of infinitely many ways to turn the list functor into a monad. The same applies to the usual [non-empty list monad](https://hackage.haskell.org/package/base-4.14.0.0/docs/src/GHC.Base.html#line-1105) and the non-empty list functor. This library collects such non-standard "list" and "non-empty list" monads.  Most of the constructions implemented in this library have been first introduced in the paper [Degrading lists](degrading-lists.pdf) by Dylan McDermott, Maciej Piróg, and Tarmo Uustalu (PPDP 2020), but there are some new specimens as well. -It is quite possible that there exist "list" and "non-empty list" monads that we are not aware of, so pull requests are appreciated. Moreover, not every monad in this library has been formally verified to be a monad (because of the combinatorial explosion of the number of cases to be considered in the proof of associativity), so if you're currently playing around with tools like Coq and have a spare afternoon...+It is quite possible that there exist "list" and "non-empty list" monads that we are not aware of, so pull requests are appreciated. Moreover, not every monad in this library has been formally verified to be a monad (it is not a trivial task because of combinatorial explosions of the number of cases to be considered in some proofs of associativity), so if you're currently playing around with tools like Coq and have a spare afternoon...

@@ -4,10 +4,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: d8bad60fc0a7573c702039797f7320d100d283efcb79d5789c85819c1c7ff760+-- hash: 5b5385de8f22ca1f51a19de7b8b393b9012fded676d9ea7412ac96fde7fc9d83  name:           exotic-list-monads-version:        1.0.0+version:        1.0.1 synopsis:       Non-standard monads on lists and non-empty lists description:    The usual list monad is only one of infinitely many ways to turn the list functor into a monad. The same applies to the usual non-empty list monad and the non-empty list functor. This library collects such non-standard "list" and "non-empty list" monads. category:       List, Monads

@@ -237,8 +237,8 @@   eps  = []   (<>) = (++) --- | A class for __free right-braketed__ (subclasses of) __pointed--- magmas__.+-- | A class for __free right-braketed__ (subclasses of)+-- __pointed magmas__. -- -- Most of the monads defined in this module arise from subclasses of -- 'PointedMagma', in which we do not assume any additional methods,@@ -395,17 +395,17 @@ -- MazeWalk "JohnhoJPauluaPGeorgegroeGRingo" -- -- It represents a walk through the following maze (the entrance is--- marked with \"▶\"):+-- marked with \">\"): -- -- @---  ┌──┬───┐---  │LU│NGO│---  ├╴A│I┌─┘---  ▶JPGR│--- ┌┘O│E┌┘--- │NH│O└─┐--- └──┤RGE│---    └───┘+--   ┌────┬──────┐+--   │L U │ N G O│+--   ├─┤A ┴ I┌───┘+--  > J P G R│+-- ┌─┘O ┬ E ┌┘+-- │N H │ O └──┐+-- └────┤ R G E│+--      └──────┘ -- @ -- -- First, we take the J-O-H-N path. When we reach its end, we turn@@ -707,12 +707,12 @@ -- @ class (KnownNat n, PointedMagma a) => StutterKeeperAlgebra n a --- | This monad arises from free stutter-keeper algebras. Its join--- stutters (as in the 'Stutter' monad) if the first non-singleton--- list in empty. Otherwise, it keeps the singleton prefix, and keeps--- the first non-singleton list. The join can thus be defined as--- follows (omitting the conversion of the type-level 'Nat' @n@ to a--- run-time value):+-- | The stutter-keeper monad arises from free stutter-keeper+-- algebras. Its join stutters (as in the 'Stutter' monad) if the+-- first non-singleton list in empty. Otherwise, it keeps the+-- singleton prefix, and keeps the first non-singleton list. The join+-- can thus be defined as follows (omitting the conversion of the+-- type-level 'Nat' @n@ to a run-time value): -- -- @ -- join xss | null xss@@ -773,7 +773,7 @@ -- The StutterStutter monad -- ------------------------------ --- | A stutter-keeper algebra (for given natural numbesr @n@ and @m@)+-- | A stutter-stutter algebra (for given natural numbers @n@ and @m@) -- is a pointed magma that satisfies the following equations: -- -- @@@ -783,7 +783,13 @@ -- @ class (KnownNat n, KnownNat m, PointedMagma a) => StutterStutterAlgebra n m a --- |+-- | The stutter-stutter monad arises from free stutter-stutter+-- algebras. It is similar to 'StutterKeeper', but instead of keeping+-- the first non-singleton list, it stutters on its first element+-- (unless the first non-singleton list is also the last list, in+-- which case it is kept in the result). The join can thus be defined+-- as follows (omitting the conversion of the type-level nats to+-- run-time values): -- -- @ -- join xss | null xss

@@ -956,6 +956,25 @@ -- 'ShortFront' construction gives a monad. class (NonEmptyMonad m) => HasShortFront m +instance HasShortFront NonEmpty++-- | (?)+instance HasShortFront Keeper++-- | (?)+instance HasShortFront OpDiscreteHybridNE++-- | (?)+instance HasShortFront MazeWalkNE++-- | (?)+instance (KnownNat n) => HasShortFront (StutterNE n)++-- | (?)+instance HasShortFront AlphaOmega++instance (HasShortRear m) => HasShortFront (DualNonEmptyMonad m)+ -- | This is a transformer for a number of monads (instances of the -- 'HasShortFront' class), whose return is singleton and join takes -- the prefix of length @p + 2@ of the result of the join of the@@ -972,6 +991,21 @@ -- lists, only one such monad on possibly-empty lists is known, -- 'Control.Monad.List.Exotic.StutterKeeper' (the short version is -- 'Control.Monad.List.Exotic.ShortStutterKeeper').+--+-- For example:+--+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortFront NonEmpty 4 Char)+-- "JohnPa"+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortFront MazeWalkNE 4 Char)+-- "Johnho"+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortFront OpDiscreteHybridNE 4 Char)+-- "JPGRin"+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortFront Keeper 4 Char)+-- "John"+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortFront (StutterNE 2) 4 Char)+-- "JJJJ"+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortFront (StutterNE 6) 4 Char)+-- "JJJJJJ" newtype ShortFront m (p :: Nat) a = ShortFront { unShortFront :: m a }  deriving (Functor, Show, Eq) @@ -982,9 +1016,8 @@ instance (HasShortFront m, KnownNat p) => Monad (ShortFront m p) where   return = ShortFront . return   ShortFront m >>= f | isSingle (unwrap m)-                     = ShortFront $ m >>= unShortFront . f-                     | nonEmptyAll isSingle-                         $ unwrap (unwrap . unShortFront . f <$> m)+                     || nonEmptyAll isSingle+                          (unwrap $ unwrap . unShortFront . f <$> m)                      = ShortFront $ m >>= unShortFront . f                      | otherwise                      = let p = fromIntegral $ natVal (Proxy :: Proxy p)@@ -1000,24 +1033,15 @@   wrap   = ShortFront . wrap   unwrap = unwrap . unShortFront -instance HasShortFront NonEmpty---- | (?)-instance HasShortFront Keeper---- | (?)-instance HasShortFront OpDiscreteHybridNE---- | (?)-instance HasShortFront MazeWalkNE---- | (?)-instance (KnownNat n) => HasShortFront (StutterNE n)+-- The following two are needed for examples in the docs: --- | (?)-instance HasShortFront AlphaOmega+instance (HasShortFront m, KnownNat p) => IsList (ShortFront m p a) where+  type Item (ShortFront m p a) = a+  fromList = wrap . fromList+  toList = toList . unwrap -instance (HasShortRear m) => HasShortFront (DualNonEmptyMonad m)+instance (HasShortFront m, KnownNat p) => IsString (ShortFront m p Char) where+  fromString = fromList  --------------------------- -- The Short Rear monad --@@ -1027,8 +1051,26 @@ -- 'ShortRear' construction gives a monad. class (NonEmptyMonad m) => HasShortRear m +instance HasShortRear NonEmpty++-- | (?)+instance HasShortRear DiscreteHybridNE++-- | (?)+instance HasShortRear AlphaOmega++instance (HasShortFront m) => HasShortRear (DualNonEmptyMonad m)+ -- | Similar to 'ShortFront', but gives a monad if restricted to a -- suffix of the length @p + 2@.+--+-- For example:+--+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortRear NonEmpty 5 Char)+-- "geRingo"+-- >>> toList $ unwrap (join ["John", "Paul", "George", "Ringo"] :: ShortRear DiscreteHybridNE 5 Char)+-- "leRingo"+-- newtype ShortRear m (p :: Nat) a = ShortRear { unShortRear :: m a }  deriving (Functor, Show, Eq) @@ -1042,9 +1084,8 @@ instance (HasShortRear m, KnownNat p) => Monad (ShortRear m p) where   return = ShortRear . return   ShortRear m >>= f | isSingle (unwrap m)-                    = ShortRear $ m >>= unShortRear . f-                    | nonEmptyAll isSingle-                        $ unwrap (unwrap . unShortRear . f <$> m)+                    || nonEmptyAll isSingle+                         (unwrap $ unwrap . unShortRear . f <$> m)                     = ShortRear $ m >>= unShortRear . f                     | otherwise                     = let p = fromIntegral $ natVal (Proxy :: Proxy p)@@ -1060,12 +1101,12 @@   wrap   = ShortRear . wrap   unwrap = unwrap . unShortRear -instance HasShortRear NonEmpty---- | (?)-instance HasShortRear DiscreteHybridNE+-- The following two are needed for examples in the docs: --- | (?)-instance HasShortRear AlphaOmega+instance (HasShortRear m, KnownNat p) => IsList (ShortRear m p a) where+  type Item (ShortRear m p a) = a+  fromList = wrap . fromList+  toList = toList . unwrap -instance (HasShortFront m) => HasShortRear (DualNonEmptyMonad m)+instance (HasShortRear m, KnownNat p) => IsString (ShortRear m p Char) where+  fromString = fromList