In this module, a "list monad" is a monad in which the underlying functor is isomorphic to List. We require:

wrap . unwrap  ==  id
unwrap . wrap  ==  id

There is a default implementation provided if m is known to be a list (meaning m a is an instance of IsList for all a).

Every list monad has a dual, in which join is defined as

reverse . join . reverse . fmap reverse

(where join is the join of the original list monad).

return is the same as in the original monad.

Checks if a given list is a singleton (= list of length one).

Pointed magmas are structures with one binary operation and one constant. In general, no laws are imposed.

A class for free right-braketed (subclasses of) pointed magmas.

All monads defined in this section arise from subclasses of PointedMagma, in which we do not assume any additional methods, but require the instances to satisfy additional equations. This means that the monad is not only an instance of such a class that defines a type of algebra, but it is free such algebra.

In particular, we consider theories c in which the equations have the following shapes:

x <> eps       ==  ...
eps <> x       ==  ...
(x <> y) <> z  ==  ...

Moreover, when read left-to-right, they form a terminating and confluent rewriting system with normal forms of the following shape:

eps
x <> (y <> ( ... (z <> t) ... ))

This class offers a witness that a particular list monad m is a free algebra of the theory c. This gives us the function

foldRBPM _ (unwrap -> []) = eps
foldRBPM f (unwrap -> xs) = foldr1 (<>) (map f xs)

which is the unique lifting of an interpretation of generators to a homomorphism (between algebras of this sort) from the list monad to any algebra (an instance) of c.

Note that the default definition of foldRBPM is always the right one for right-bracketed subclasses of PointedMagma, so it is enough to declare the relationship, for example:

instance FreeRBPM [] Monoid

A zero semigroup has an associative binary operation and a constant that is absorbing on both sides. That is, the following equations hold:

x <> eps       ==  eps
eps <> x       ==  eps
(x <> y) <> z  ==  x <> (y <> z)

The Global Failure monad arises from free zero semigroups. It implements a kind of nondeterminism similar to the usual List monad, but failing (= resulting in the empty list) in one branch makes the entire computation fail. Its join is defined as:

join xss | any null xss = []
         | otherwise    = concat xss

For example:

>>> [1, 2, 3] >>= (\n -> [1..n]) :: GlobalFailure Int
GlobalFailure [1,1,2,1,2,3]
>>> [1, 0, 3] >>= (\n -> [1..n]) :: GlobalFailure Int
GlobalFailure []

A palindrome algebra is a pointed magma that satisfies the following equations:

x <> eps       ==  eps
eps <> x       ==  eps
(x <> y) <> z  ==  x <> (y <> (x <> z))

Turns a list into a palindrome by appending it and its reversed init. For example:

palindromize []       ==  []
palindromize "Ringo"  ==  "RingogniR"

The Maze Walk monad arises from free palindrome algebras. Its join is defined as:

join xss | null xss     = []
         | any null xss = []
         | otherwise    = concatMap palindromize (init xss) ++ last xss

Intuitively, it is a list of values one encounters when walking a path in a maze. The bind operation attaches to each value a new "corridor" to visit. In our walk we explore every such corridor. For example, consider the following expression:

>>> join ["John", "Paul", "George", "Ringo"] :: MazeWalk Char
MazeWalk "JohnhoJPauluaPGeorgegroeGRingo"

It represents a walk through the following maze (the entrance is marked with ">"):

  ┌────┬──────┐
  │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 around and go back to J, so our walk to this point is J-O-H-N-H-O-J (hence the connection with palindromes). Then, we explore the P-A-U-L corridor, adding P-A-U-L-U-A-P to our walk. The same applies to G-E-O-R-G-E. But when at the end of R-I-N-G-O, we have explored the entire maze, so our walk is done (this is why we do not palindromize the last element).

Instances should satisfy the following:

x <> eps       ==  eps
eps <> x       ==  x
(x <> y) <> z  ==  y <> z

A singleton list with the last element of the argument, if it exists. Otherwise, empty.

safeLast "Roy"  ==  "y"
safeLast []     ==  []

The Discrete Hybrid monad arises from free leaning algebras. Its join is defined as:

join xss | null xss        = []
         | null (last xss) = []
         | otherwise       = concatMap safeLast (init xss) ++ last xss

For example:

>>> join ["Roy", "Kelton", "Orbison"] :: DiscreteHybrid Char
DiscreteHybrid "ynOrbison"
>>> join ["Roy", "", "Orbison"] :: DiscreteHybrid Char
DiscreteHybrid "yOrbison"

A skewed algebra allows only right-nested composition of the binary operation. Every other expression is equal to eps.

x <> eps       ==  eps
eps <> x       ==  eps
(x <> y) <> z  ==  eps

The List Unfold monad arises from free skewed algebras. It implements a form of nondeterminism similar to the usual list monad, but new choices may arise only in the last element (so the bind operation can only rename other elements), essentially unfolding a list. If new choices arise in the "init" of the list, the entire computation fails. Also, failure is always global. The join operation is defined as follows:

join xss | null xss                        = []
         | any null xss                    = []
         | any (not . isSingle) (init xss) = []
         | otherwise                       = concat xss

For example:

>>> [1,1,1,4] >>= \x -> [1..x] :: ListUnfold Int
ListUnfold [1,1,1,1,2,3,4]
>>> [1,2,1,4] >>= \x -> [1..x] :: ListUnfold Int
ListUnfold []
>>> [1,0,1,4] >>= \x -> [1..x] :: ListUnfold Int
ListUnfold []

A stutter algebra (for a given natural number n) is a pointed magma that satisfies the following equations:

x <> eps       ==  foldr1 (<>) (replicate (n + 2) x)
eps <> x       ==  eps  
(x <> y) <> z  ==  eps

Repeat the last element on the list n additional times, that is:

replicateLast n [] = []
replicateLast n xs = xs ++ replicate n (last xs)

The Stutter monad arises from free stutter algebras. Its join is a concat of the longest prefix consisting only of singletons with a "stutter" on the last singleton (that is, the last singleton is additionally repeated n+1 times for an n fixed in the type). It doesn't stutter only when the init consists only of singletons and the last list is non-empty. 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
         = []
         | any (not . isSingle) (init xss) || null (last xss)
         = replicateLast (n + 1) (concat $ takeWhile isSingle (init xss))
         | otherwise
         = concat xss

The Stutter monad is quite similar to ListUnfold. The difference is that when the latter fails (that is, its join results in the empty list), the former stutters on the last singleton.

Examples:

>>> join ["1", "2", "buckle", "my", "shoe"] :: Stutter 5 Char
Stutter "12222222"
>>> join ["1", "2", "buckle"] :: Stutter 5 Char
Stutter "12buckle"
>>> join ["1", "2", "", "my", "shoe"] :: Stutter 5 Char
Stutter "12222222"

A stutter-keeper algebra (for a given natural number n) is a pointed magma that satisfies the following equations:

x <> eps       ==  foldr1 (<>) (replicate (n + 2) x)
eps <> x       ==  eps  
(x <> y) <> z  ==  x <> y

The stutter-keeper monad arises from free stutter-keeper algebras. Its join stutters (as in the Stutter monad) if the first non-singleton list is 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
         = []
         | null (head (dropWhile isSingle (init xss) ++ [last xss]))
         = replicateLast (n + 1) (concat $ takeWhile isSingle (init xss))
         | otherwise
         = map head (takeWhile isSingle (init xss))
            ++ head (dropWhile isSingle (init xss) ++ [last xss])

Examples:

>>> join ["1", "2", "buckle", "my", "shoe"] :: StutterKeeper 5 Char
StutterKeeper "12buckle"
>>> join ["1", "2", "buckle"] :: StutterKeeper 5 Char
StutterKeeper "12buckle"
>>> join ["1", "2", "", "my", "shoe"] :: StutterKeeper 5 Char
StutterKeeper "12222222"

A stutter-stutter algebra (for given natural numbers n and m) is a pointed magma that satisfies the following equations:

x <> eps       ==  foldr1 (<>) (replicate (n + 2) x)
eps <> x       ==  eps  
(x <> y) <> z  ==  foldr1 (<>) (replicate (m + 2) x)

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
         = []
         | null (head (dropWhile isSingle (init xss) ++ [last xss]))
         = replicateLast (n + 1) (concat $ takeWhile isSingle (init xss))
         | any (not . isSingle) (init xss) || null (last xss)
         = concat (takeWhile isSingle (init xss))
            ++ replicate (m + 2) (head (head (dropWhile isSingle (init xss))))
         | otherwise
         = concat xss

Examples:

>>> join ["1", "2", "buckle", "my", "shoe"] :: StutterStutter 5 10 Char
StutterStutter "12bbbbbbbbbbbb"
>>> join ["1", "2", "buckle"] :: StutterStutter 5 10 Char
StutterStutter "12buckle"
>>> join ["1", "2", "", "my", "shoe"] :: StutterStutter 5 10 Char
StutterStutter "12222222"

The Mini monad is, in a sense, a minimal list monad, meaning that its join fails (= results in the empty list) for all values except the ones that appear in the unit laws (i.e., a singleton or a list of singletons):

join xss | isSingle xss || all isSingle xss = concat xss
         | otherwise                        = []

For example:

>>> join ["HelloThere"] :: Mini Char
Mini "HelloThere"
>>> join ["Hello", "There"] :: Mini Char
Mini ""
>>> join ["H", "T"] :: Mini Char
Mini "HT"

This monad arises from the numerical monoid \(\{0\}\).

It does not arise from a subclass of PointedMagma (or any algebraic theory with a finite number of operations for that matter).

The join of the Odd monad is a concat of the inner lists provided there is an odd number of them, and that all of them are of odd length themselves. Otherwise (modulo cases needed for the unit laws), the result is the empty list.

join xss | isSingle xss || all isSingle xss  = concat xss
         | odd (length xss)
            && all (odd . length) xss        = concat xss 
         | otherwise                         = []

For example:

>>> join ["Elvis", "Presley"] :: Odd Char
Odd ""
>>> join ["Elvis", "Aaron", "Presley"] :: Odd Char
Odd "ElvisAaronPresley"
>>> join ["Roy", "Kelton", "Orbison"] :: Odd Char
Odd ""

It arises from the numerical monoid \(\{0,2,4,6,\ldots\}\). -- Note that the sum of even numbers is always even, which cannot be said of odd numbers!

At the moment, it is unclear whether it comes from a finite algebraic theory.

The join of the AtLeast n monad is a concat of the inner lists provided there are at least n inner lists and all the inner lists are of length at least n or 1 (plus the cases required by the unit laws).

The join can thus be defined as follows (omitting the conversion of the type-level nats to run-time values):

join xss | isSingle xss || all isSingle xss  = concat xss
         | otherwise = let ok :: forall x. [x] -> Bool
                           ok xs = length xs >= n || length xs == 1
                       in if ok xss && all ok xss
                            then concat xss
                            else []

For example:

>>> join ["Strawberry", "Fields", "Forever"] :: AtLeast 3 Char
AtLeast "StrawberryFieldsForever"
>>> join ["All", "You", "Need", "Is", "Love"] :: AtLeast 3 Char
AtLeast []
>>> join ["I", "Want", "You"] :: AtLeast 3 Char
AtLeast "IWantYou"
>>> join ["I", "Am", "The", "Walrus"] :: AtLeast 3 Char
AtLeast []

The monad AtLeast n arises from the numerical monoid \(\{0, n-1, n, n+1, n+2,\ldots\}\).

An interesting property of numerical monoids is that they are always finitely generated. This means that every numerical monoid can be constructed by starting out with a finite set of nautral numbers and closing it under addition. For example, the set \(\{0,2,4,6,\ldots\}\) is generated by \(\{2\}\), because every even number is of the form \(2k\) for some \(k\).

The class NumericalMonoidGenerators represents a set of generators given as a type-level list of nats.

The monad generated by the numerical monoid generated by a set of generators ns.

join xss | null xss || any null xss                                     = []
         | isInNumericalMonoid @ns (length xss - 1)
            && all (\xs -> isInNumericalMonoid @ns (length xs - 1)) xss = concat xss
         | otherwise                                                    = []

In particular:

• Mini is equivalent to NumericalMonoidMonad '[],
• GlobalFailure is equivalent to NumericalMonoidMonad '[1],
• Odd is equivalent to NumericalMonoidMonad '[2],
• AtLeast n is equivalent to NumericalMonoidMonad '[n-1, n, n+1, ..., 2n-3].

The monad whose join is concat, but only if the total length of the list (that is, the sum of the lengths of the inner lists) is not greater than n (except for the unit laws and the "global failure" property):

join xss | isSingle xss || all isSingle xss = concat xss
         | any null xss                     = []
         | length (concat xss) <= n         = concat xss
         | otherwise                        = []

For example:

>>> join ["El","vis"] :: AtMost 5 Char
AtMost "Elvis"
>>> join ["El","v","i"] :: AtMost 5 Char
AtMost "Elvi"
>>> join ["El","","vis"] :: AtMost 5 Char
AtMost ""
>>> join ["Presley"] :: AtMost 5 Char
AtMost "Presley"
>>> join ["P","r","e","s","l","e","y"] :: AtMost 5 Char
AtMost "Presley"
>>> join ["Pre","s","ley"] :: AtMost 5 Char
AtMost ""

The SetOfNats class defines a subset of the set of natural numbers (from which we are actually interested in odd numbers only). We give two instances, Primes and Fib, as examples, so if one wants to construct their own monad, they need to define an instance first: any total elemOf gives a monad.

For example:

>>> filter (elemOf @"Primes") [0..100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
>>> filter (elemOf @"Fib") [0..100]
[0,1,2,3,5,8,13,21,34,55,89]

The ContinuumOfMonads monad is parameterised by a set of natural numbers (a symbol that instantiates SetOfNats).

The join of ContinuumOfMonads s is defined as follows:

join xss       | isSingle xss    || all isSingle xss      = concat xss
               | null xss        || any null xss          = []
join [[x], xs] | odd (length xs) && elemOf @s (length xs) = x : xs
join _                                                    = []

For example:

>>> join [[0],[1,2,3]] :: ContinuumOfMonads "Primes" Int
ContinuumOfMonads [0,1,2,3]
>>> join [[0],[1,2,3,4]] :: ContinuumOfMonads "Primes" Int
ContinuumOfMonads []
>>> join [[0,1],[1,2,3,4,5]] :: ContinuumOfMonads "Primes" Int
ContinuumOfMonads []

This monad works just like the StutterKeeper monad but it takes a prefix of the result of join of length p+2 (unless the unit laws say otherwise). Thus, its join is defined as follows (omitting the conversion of the type-level Nat p to a run-time value):

join xss | isSingle xss     = concat xss
         | all isSingle xss = concat xss
         | otherwise        = take (p + 2) $ toList
                                ((Control.Monad.join $ StutterKeeper $ fmap StutterKeeper xss)
                                  :: StutterKeeper n _)

For example:

>>> join ["1", "2", "buckle", "my", "shoe"] :: ShortStutterKeeper 5 2 Char
ShortStutterKeeper "12bu"
>>> join ["1", "2", "buckle"] :: ShortStutterKeeper 5 2 Char
ShortStutterKeeper "12bu"
>>> join ["1", "2", "", "my", "shoe"] :: ShortStutterKeeper 5 2 Char
ShortStutterKeeper "1222"

Compare the ShortFront monad on non-empty lists.