Copyright  (c) Dylan McDermott Maciej Piróg Tarmo Uustalu 2020 

License  MIT 
Maintainer  maciej.adam.pirog@gmail.com 
Stability  experimental 
Portability  portable 
Safe Haskell  Trustworthy 
Language  Haskell2010 
The usual list monad is only one of infinitely many ways to turn the List functor into a monad. This module collects a number of such nonstandard "list" monads.
Notes:
 Types marked with "(?)" have not been formally verified to be monads (yet), though they were thoroughly tested with billions of QuickCheck tests.
 Monads in this module are defined in terms of
join
rather than>>=
. Thereturn
of every monad is singleton (it is not known if there exists a monad on lists with a different return).  For readability, code snippets in this documentation assume the
OverloadedLists
andOverloadedStrings
language extensions, which make it possible to omit somenewtype
constructors. Example definitions of joins of monads always skip thenewtype
constructors, that is, assume>>=
is always defined as follows for a particular localjoin
:
m>>=
f =wrap
$ join $map
(unwrap
. f) $unwrap
m where join = ...
 The definitions of monads are optimized for readability and not runtime performance. This is because the monads in this module don't seem to be of any practical use, they are more of a theoretical curiosity.
References:
Most of the monads defined in this module have been introduced in the following papers (although there are some new specimens as well):
 Degrading Lists by Dylan McDermott, Maciej Piróg, Tarmo Uustalu (PPDP 2020),
 Counting Monads on Lists by Dylan McDermott, Maciej Piróg, Tarmo Uustalu (CLA 2023),
 Hybrid Programs by Renato Neves (PhD Thesis, 2018).
Synopsis
 class Monad m => ListMonad m where
 newtype DualListMonad m a = DualListMonad {
 unDualListMonad :: m a
 isSingle :: [a] > Bool
 class PointedMagma a where
 class ListMonad m => FreeRBPM m (c :: * > Constraint)  m > c where
 foldRBPM :: (PointedMagma a, c a) => (x > a) > m x > a
 class PointedMagma a => ZeroSemigroup a
 newtype GlobalFailure a = GlobalFailure {
 unGlobalFailure :: [a]
 class PointedMagma a => PalindromeAlgebra a
 palindromize :: [a] > [a]
 newtype MazeWalk a = MazeWalk {
 unMazeWalk :: [a]
 class PointedMagma a => LeaningAlgebra a
 safeLast :: [a] > [a]
 newtype DiscreteHybrid a = DiscreteHybrid {
 unDiscreteHybrid :: [a]
 class PointedMagma a => SkewedAlgebra a
 newtype ListUnfold a = ListUnfold {
 unListUnfold :: [a]
 class (KnownNat n, PointedMagma a) => StutterAlgebra n a
 replicateLast :: Int > [a] > [a]
 newtype Stutter (n :: Nat) a = Stutter {
 unStutter :: [a]
 class (KnownNat n, PointedMagma a) => StutterKeeperAlgebra n a
 newtype StutterKeeper (n :: Nat) a = StutterKeeper {
 unStutterKeeper :: [a]
 class (KnownNat n, KnownNat m, PointedMagma a) => StutterStutterAlgebra n m a
 newtype StutterStutter (n :: Nat) (m :: Nat) a = StutterStutter {
 unStutterStutter :: [a]
 newtype Mini a = Mini {
 unMini :: [a]
 newtype Odd a = Odd {
 unOdd :: [a]
 newtype AtLeast (n :: Nat) a = AtLeast {
 unAtLeast :: [a]
 class NumericalMonoidGenerators (ns :: [Nat]) where
 isInNumericalMonoid :: Int > Bool
 newtype NumericalMonoidMonad (ns :: [Nat]) a = NumericalMonoidMonad {
 unNumericalMonoidMonad :: [a]
 newtype AtMost (n :: Nat) a = AtMost {
 unAtMost :: [a]
 class SetOfNats (a :: Symbol) where
 newtype ContinuumOfMonads (s :: Symbol) a = ContinuumOfMonads {
 unContinuumOfMonads :: [a]
 newtype ShortStutterKeeper (n :: Nat) (p :: Nat) a = ShortStutterKeeper {
 unShortStutterKeeper :: [a]
List monads in general
class Monad m => ListMonad m where Source #
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
).
Nothing
Instances
newtype DualListMonad m a Source #
Every list monad has a dual, in which join is defined as
join . reverse . fmap reverse
(where join is the join of the original list monad), while return is
reverse . return
(where return is the return of the original list monad).
DualListMonad  

Instances
Monads with finite presentation
This section contains monads that come about from free algebras of
theories with a finite number of operations, represented as type
classes. Coincidentally, all theories in this module have one
binary and one nullary operation, that is, each is a subclass of
PointedMagma with additional laws. (So does the usual list monad,
where the subclass is monoid.) It is not known if there exists a
list monad that has a finite presentation but necessarily with a
different set of operations (there are such monads on nonempty
lists, for example, HeadTails
and HeadsTail
).
Pointed magmas
class PointedMagma a where Source #
Pointed magmas are structures with one binary operation and one constant. In general, no laws are imposed.
Instances
class ListMonad m => FreeRBPM m (c :: * > Constraint)  m > c where Source #
A class for free rightbraketed (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,
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 lefttoright, 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 rightbracketed subclasses of PointedMagma
, so it is
enough to declare the relationship, for example:
instance FreeRBPM [] Monoid
Nothing
foldRBPM :: (PointedMagma a, c a) => (x > a) > m x > a Source #
Instances
The Global Failure monad
class PointedMagma a => ZeroSemigroup a Source #
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)
Instances
FreeRBPM GlobalFailure ZeroSemigroup Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, ZeroSemigroup a) => (x > a) > GlobalFailure x > a Source #  
ZeroSemigroup (GlobalFailure a) Source #  
Defined in Control.Monad.List.Exotic 
newtype GlobalFailure a Source #
The Global Failure monad arises from free zero semigroups. It implements a kind of nondeterminism similar to the usual List monad, but failing (= producing an 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 []
GlobalFailure  

Instances
The Maze Walk monad
class PointedMagma a => PalindromeAlgebra a Source #
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))
Instances
FreeRBPM MazeWalk PalindromeAlgebra Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, PalindromeAlgebra a) => (x > a) > MazeWalk x > a Source #  
PalindromeAlgebra (MazeWalk a) Source #  
Defined in Control.Monad.List.Exotic 
palindromize :: [a] > [a] Source #
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 JOHN path. When we reach its end, we turn around and go back to J, so our walk to this point is JOHNHOJ (hence the connection with palindromes). Then, we explore the PAUL corridor, adding PAULUAP to our walk. The same applies to GEORGE. But when at the end of RINGO, we have explored the entire maze, so our walk is done (this is why we do not palindromize the last element).
MazeWalk  

Instances
Applicative MazeWalk Source #  
Functor MazeWalk Source #  
Monad MazeWalk Source #  
ListMonad MazeWalk Source #  
FreeRBPM MazeWalk PalindromeAlgebra Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, PalindromeAlgebra a) => (x > a) > MazeWalk x > a Source #  
IsString (MazeWalk Char) Source #  
Defined in Control.Monad.List.Exotic fromString :: String > MazeWalk Char #  
IsList (MazeWalk a) Source #  
Show a => Show (MazeWalk a) Source #  
PalindromeAlgebra (MazeWalk a) Source #  
Defined in Control.Monad.List.Exotic  
PointedMagma (MazeWalk a) Source #  
Eq a => Eq (MazeWalk a) Source #  
type Item (MazeWalk a) Source #  
Defined in Control.Monad.List.Exotic 
The Discrete Hybrid monad
class PointedMagma a => LeaningAlgebra a Source #
Instances
FreeRBPM DiscreteHybrid LeaningAlgebra Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, LeaningAlgebra a) => (x > a) > DiscreteHybrid x > a Source #  
LeaningAlgebra (DiscreteHybrid a) Source #  
Defined in Control.Monad.List.Exotic 
safeLast :: [a] > [a] Source #
A singleton list with the last element of the argument, if it exists. Otherwise, empty.
safeLast "Roy" == "y" safeLast [] == []
newtype DiscreteHybrid a Source #
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"
DiscreteHybrid  

Instances
The List Unfold monad
class PointedMagma a => SkewedAlgebra a Source #
A skewed algebra allows only rightnested composition of the
binary operation. Every other expression is equal to eps
.
x<>
eps
==eps
eps
<>
x ==eps
(x<>
y)<>
z ==eps
Instances
FreeRBPM ListUnfold SkewedAlgebra Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, SkewedAlgebra a) => (x > a) > ListUnfold x > a Source #  
SkewedAlgebra (ListUnfold a) Source #  
Defined in Control.Monad.List.Exotic 
newtype ListUnfold a Source #
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 []
ListUnfold  

Instances
The Stutter monad
class (KnownNat n, PointedMagma a) => StutterAlgebra n a Source #
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
Instances
KnownNat n => StutterAlgebra n (Stutter n a) Source #  
Defined in Control.Monad.List.Exotic  
KnownNat n => FreeRBPM (Stutter n) (StutterAlgebra n) Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, StutterAlgebra n a) => (x > a) > Stutter n x > a Source # 
replicateLast :: Int > [a] > [a] Source #
Repeat the last element on the list n
additional times, that is:
replicateLast n [] = [] replicateLast n xs = xs ++ replicate n (last xs)
newtype Stutter (n :: Nat) a Source #
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 nonempty. The join can thus be defined as follows
(omitting the conversion of the typelevel Nat
n
to a runtime
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 an 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"
Instances
KnownNat n => StutterAlgebra n (Stutter n a) Source #  
Defined in Control.Monad.List.Exotic  
KnownNat n => Applicative (Stutter n) Source #  
Functor (Stutter n) Source #  
KnownNat n => Monad (Stutter n) Source #  
KnownNat n => ListMonad (Stutter n) Source #  
KnownNat n => FreeRBPM (Stutter n) (StutterAlgebra n) Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, StutterAlgebra n a) => (x > a) > Stutter n x > a Source #  
KnownNat n => IsString (Stutter n Char) Source #  
Defined in Control.Monad.List.Exotic fromString :: String > Stutter n Char #  
KnownNat n => IsList (Stutter n a) Source #  
Show a => Show (Stutter n a) Source #  
KnownNat n => PointedMagma (Stutter n a) Source #  
Eq a => Eq (Stutter n a) Source #  
type Item (Stutter n a) Source #  
Defined in Control.Monad.List.Exotic 
The StutterKeeper monad
class (KnownNat n, PointedMagma a) => StutterKeeperAlgebra n a Source #
A stutterkeeper 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
Instances
KnownNat n => StutterKeeperAlgebra n (StutterKeeper n a) Source #  
Defined in Control.Monad.List.Exotic  
KnownNat n => FreeRBPM (StutterKeeper n) (StutterKeeperAlgebra n) Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, StutterKeeperAlgebra n a) => (x > a) > StutterKeeper n x > a Source # 
newtype StutterKeeper (n :: Nat) a Source #
The stutterkeeper monad arises from free stutterkeeper
algebras. Its join stutters (as in the Stutter
monad) if the
first nonsingleton list in empty. Otherwise, it keeps the
singleton prefix, and keeps the first nonsingleton list. The join
can thus be defined as follows (omitting the conversion of the
typelevel Nat
n
to a runtime 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"
StutterKeeper  

Instances
The StutterStutter monad
class (KnownNat n, KnownNat m, PointedMagma a) => StutterStutterAlgebra n m a Source #
A stutterstutter 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)
Instances
(KnownNat n, KnownNat m) => StutterStutterAlgebra n m (StutterStutter n m a) Source #  
Defined in Control.Monad.List.Exotic  
(KnownNat n, KnownNat m) => FreeRBPM (StutterStutter n m) (StutterStutterAlgebra n m) Source #  
Defined in Control.Monad.List.Exotic foldRBPM :: (PointedMagma a, StutterStutterAlgebra n m a) => (x > a) > StutterStutter n m x > a Source # 
newtype StutterStutter (n :: Nat) (m :: Nat) a Source #
The stutterstutter monad arises from free stutterstutter
algebras. It is similar to StutterKeeper
, but instead of keeping
the first nonsingleton list, it stutters on its first element
(unless the first nonsingleton 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 typelevel nats to
runtime 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"
StutterStutter  

Instances
Monads from numerical monoids
A numerical monoid is a subset of the set of natural numbers that contains 0 and is closed under addition. That is, \(M \subseteq \mathbb N\) is a numerical monoid if
 \(0 \in M\),
 if \(x,y \in M\), then \(x+y \in M\).
Representing a numerical monoid \(M\) using its characteristic
function m :: Int > Bool
(revealing if a given number belongs to
\(M\)), we can define a monad as follows:
join xss  isSingle xss  all isSingle xss = concat xss  null xss  any null xss = []  m (length xss  1) && all (\xs > m $ length xs  1) xss = concat xss  otherwise = []
There is also some intuition behind the " 1
" part: For a set \(M \subseteq \mathbb N\),
we define a set shifted by 1 as \(M^{+} =\{x \in \mathbb N \ \ x1 \in M\}\).
Then, \(M\) is a numerical monoid if and only if:
 \(1 \in M^{+}\),
 if \(n, x_1, \ldots, x_n \in M^{+}\), then \(\displaystyle \sum_{i = 0}^n x_i \in M^{+}\).
(Do note that in the above \(n\) is in \(M^{+}\) as well!) This
means that \(M^{+}\) is a set of "accepted lengths" of lists, while
the condition above states that when we concatenate an accepted
number of accepted lists, we still obtain an accepted list. This in
turn can be used to prove the associativity law for monads: breadly
speaking, join :: [[[a]]] > [a]
is a concat only if all the
lists on all levels are of accepted lengths (save for the unit
laws), and joining (either the inner lists or the outer list first)
will not produce a nonaccepted list.
Below, we first show a couple of concrete examples of monads arising from particular numerical monoids, and then the general version via a set of generators.
The Mini monad
The Mini monad is, in a sense, a minimal list monad, meaning that its join fails (= results in an 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).
Instances
Applicative Mini Source #  
Functor Mini Source #  
Monad Mini Source #  
ListMonad Mini Source #  
IsString (Mini Char) Source #  
Defined in Control.Monad.List.Exotic fromString :: String > Mini Char #  
IsList (Mini a) Source #  
Show a => Show (Mini a) Source #  
Eq a => Eq (Mini a) Source #  
type Item (Mini a) Source #  
Defined in Control.Monad.List.Exotic 
The Odd monad
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), it returns an 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.
Instances
Applicative Odd Source #  
Functor Odd Source #  
Monad Odd Source #  
ListMonad Odd Source #  
IsString (Odd Char) Source #  
Defined in Control.Monad.List.Exotic fromString :: String > Odd Char #  
IsList (Odd a) Source #  
Show a => Show (Odd a) Source #  
Eq a => Eq (Odd a) Source #  
type Item (Odd a) Source #  
Defined in Control.Monad.List.Exotic 
The At Least monad
newtype AtLeast (n :: Nat) a Source #
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 typelevel nats to runtime 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, n1, n, n+1, n+2,\ldots\}\).
Instances
KnownNat n => Applicative (AtLeast n) Source #  
Functor (AtLeast n) Source #  
KnownNat n => Monad (AtLeast n) Source #  
KnownNat n => ListMonad (AtLeast n) Source #  
KnownNat n => IsString (AtLeast n Char) Source #  
Defined in Control.Monad.List.Exotic fromString :: String > AtLeast n Char #  
KnownNat n => IsList (AtLeast n a) Source #  
Show a => Show (AtLeast n a) Source #  
Eq a => Eq (AtLeast n a) Source #  
type Item (AtLeast n a) Source #  
Defined in Control.Monad.List.Exotic 
The Numerical Monoid monad
class NumericalMonoidGenerators (ns :: [Nat]) where Source #
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
represents a set of
generators given as a typelevel list of nats.NumericalMonoidGenerators
isInNumericalMonoid :: Int > Bool Source #
Check if a given number is in the numerical monoid generatted
by ns
. It is the characteristic function of the generated
numerical monoid.
Instances
NumericalMonoidGenerators ('[] :: [Nat]) Source #  
Defined in Control.Monad.List.Exotic isInNumericalMonoid :: Int > Bool Source #  
(KnownNat g, NumericalMonoidGenerators gs) => NumericalMonoidGenerators (g ': gs) Source #  
Defined in Control.Monad.List.Exotic isInNumericalMonoid :: Int > Bool Source # 
newtype NumericalMonoidMonad (ns :: [Nat]) a Source #
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:
is equivalent toMini
NumericalMonoidMonad '[]
,
is equivalent toGlobalFailure
NumericalMonoidMonad '[1]
,
is equivalent toOdd
NumericalMonoidMonad '[2]
,
is equivalent toAtLeast
nNumericalMonoidMonad '[n1, n, n+1, ..., 2n3]
.
Instances
Other list monads
The At Most monad
newtype AtMost (n :: Nat) a Source #
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 ""
Instances
KnownNat n => Applicative (AtMost n) Source #  
Functor (AtMost n) Source #  
KnownNat n => Monad (AtMost n) Source #  
KnownNat n => ListMonad (AtMost n) Source #  
KnownNat n => IsString (AtMost n Char) Source #  
Defined in Control.Monad.List.Exotic fromString :: String > AtMost n Char #  
KnownNat n => IsList (AtMost n a) Source #  
Show a => Show (AtMost n a) Source #  
Eq a => Eq (AtMost n a) Source #  
type Item (AtMost n a) Source #  
Defined in Control.Monad.List.Exotic 
The ContinuumofMonads monad
The "Continuum of Monads" monad construction was introduced in this paper to show that the set of list monads is a continuum (that is, that there are as many list monads in the category of sets as there are real numbers, and more than there are natural numbers).
We define a family of monads
, which is
parameterised by a subset of the set of natural numbers
(ContinuumOfMonads
).SetOfNats
class SetOfNats (a :: Symbol) where Source #
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
gives a monad.elemOf
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]
newtype ContinuumOfMonads (s :: Symbol) a Source #
The
monad is parameterised by a set of
natural numbers (a symbol that instantiates ContinuumOfMonads
).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 []
Instances
The Short StutterKeeper monad (?)
newtype ShortStutterKeeper (n :: Nat) (p :: Nat) a Source #
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 typelevel Nat
p
to a runtime 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 nonempty lists.