Control.Monad.List.Exotic

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 non-standard "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 >>=. The return 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 and OverloadedStrings language extensions, which make it possible to omit some newtype constructors. Example definitions of joins of monads always skip the newtype constructors, that is, assume >>= is always defined as follows for a particular local join:

m >>= f = wrap $ join $ map (unwrap . f) $ unwrap m
 where
  join = ...

• The definitions of monads are optimized for readability and not run-time 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).

List monads in general

class Monad m => ListMonad m where

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).

Minimal complete definition

Nothing

Methods

wrap :: [a] -> m a

default wrap :: (IsList (m a), Item (m a) ~ a) => [a] -> m a

unwrap :: m a -> [a]

default unwrap :: (IsList (m a), Item (m a) ~ a) => m a -> [a]

Instances

ListMonad DiscreteHybrid

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> DiscreteHybrid a

unwrap :: DiscreteHybrid a -> [a]

ListMonad GlobalFailure

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> GlobalFailure a

unwrap :: GlobalFailure a -> [a]

ListMonad ListUnfold

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> ListUnfold a

unwrap :: ListUnfold a -> [a]

ListMonad MazeWalk

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> MazeWalk a

unwrap :: MazeWalk a -> [a]

ListMonad Mini

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> Mini a

unwrap :: Mini a -> [a]

ListMonad Odd

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> Odd a

unwrap :: Odd a -> [a]

ListMonad []

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> [a]

unwrap :: [a] -> [a]

KnownNat n => ListMonad (AtLeast n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> AtLeast n a

unwrap :: AtLeast n a -> [a]

KnownNat n => ListMonad (AtMost n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> AtMost n a

unwrap :: AtMost n a -> [a]

SetOfNats s => ListMonad (ContinuumOfMonads s)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> ContinuumOfMonads s a

unwrap :: ContinuumOfMonads s a -> [a]

NumericalMonoidGenerators ns => ListMonad (NumericalMonoidMonad ns)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> NumericalMonoidMonad ns a

unwrap :: NumericalMonoidMonad ns a -> [a]

KnownNat n => ListMonad (Stutter n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> Stutter n a

unwrap :: Stutter n a -> [a]

KnownNat n => ListMonad (StutterKeeper n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> StutterKeeper n a

unwrap :: StutterKeeper n a -> [a]

ListMonad m => ListMonad (DualListMonad m)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> DualListMonad m a

unwrap :: DualListMonad m a -> [a]

(KnownNat n, KnownNat p) => ListMonad (ShortStutterKeeper n p)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> ShortStutterKeeper n p a

unwrap :: ShortStutterKeeper n p a -> [a]

(KnownNat n, KnownNat m) => ListMonad (StutterStutter n m)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> StutterStutter n m a

unwrap :: StutterStutter n m a -> [a]

newtype DualListMonad m a

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).

Constructors

DualListMonad

Fields

• unDualListMonad :: m a

Instances

ListMonad m => Applicative (DualListMonad m)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> DualListMonad m a

(<*>) :: DualListMonad m (a -> b) -> DualListMonad m a -> DualListMonad m b

liftA2 :: (a -> b -> c) -> DualListMonad m a -> DualListMonad m b -> DualListMonad m c

(*>) :: DualListMonad m a -> DualListMonad m b -> DualListMonad m b

(<*) :: DualListMonad m a -> DualListMonad m b -> DualListMonad m a

Functor m => Functor (DualListMonad m)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> DualListMonad m a -> DualListMonad m b

(<$) :: a -> DualListMonad m b -> DualListMonad m a

ListMonad m => Monad (DualListMonad m)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: DualListMonad m a -> (a -> DualListMonad m b) -> DualListMonad m b

(>>) :: DualListMonad m a -> DualListMonad m b -> DualListMonad m b

return :: a -> DualListMonad m a

ListMonad m => ListMonad (DualListMonad m)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> DualListMonad m a

unwrap :: DualListMonad m a -> [a]

(ListMonad m, IsList (m a)) => IsList (DualListMonad m a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (DualListMonad m a)

Methods

fromList :: [Item (DualListMonad m a)] -> DualListMonad m a

fromListN :: Int -> [Item (DualListMonad m a)] -> DualListMonad m a

toList :: DualListMonad m a -> [Item (DualListMonad m a)]

type Item (DualListMonad m a)

Defined in Control.Monad.List.Exotic

type Item (DualListMonad m a) = Item (m a)

isSingle :: [a] -> Bool

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

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 non-empty lists, for example, HeadTails and HeadsTail).

Pointed magmas

class PointedMagma a where

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

Methods

eps :: a

(<>) :: a -> a -> a

Instances

PointedMagma (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

Methods

eps :: DiscreteHybrid a

(<>) :: DiscreteHybrid a -> DiscreteHybrid a -> DiscreteHybrid a

PointedMagma (GlobalFailure a)

Defined in Control.Monad.List.Exotic

Methods

eps :: GlobalFailure a

(<>) :: GlobalFailure a -> GlobalFailure a -> GlobalFailure a

PointedMagma (ListUnfold a)

Defined in Control.Monad.List.Exotic

Methods

eps :: ListUnfold a

(<>) :: ListUnfold a -> ListUnfold a -> ListUnfold a

PointedMagma (MazeWalk a)

Defined in Control.Monad.List.Exotic

Methods

eps :: MazeWalk a

(<>) :: MazeWalk a -> MazeWalk a -> MazeWalk a

PointedMagma [a]

Defined in Control.Monad.List.Exotic

Methods

eps :: [a]

(<>) :: [a] -> [a] -> [a]

KnownNat n => PointedMagma (Stutter n a)

Defined in Control.Monad.List.Exotic

Methods

eps :: Stutter n a

(<>) :: Stutter n a -> Stutter n a -> Stutter n a

KnownNat n => PointedMagma (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

Methods

eps :: StutterKeeper n a

(<>) :: StutterKeeper n a -> StutterKeeper n a -> StutterKeeper n a

(KnownNat n, KnownNat m) => PointedMagma (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

Methods

eps :: StutterStutter n m a

(<>) :: StutterStutter n m a -> StutterStutter n m a -> StutterStutter n m a

class ListMonad m => FreeRBPM m (c :: * -> Constraint) | m -> c where

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, 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

Minimal complete definition

Nothing

Methods

foldRBPM :: (PointedMagma a, c a) => (x -> a) -> m x -> a

Instances

FreeRBPM DiscreteHybrid LeaningAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, LeaningAlgebra a) => (x -> a) -> DiscreteHybrid x -> a

FreeRBPM GlobalFailure ZeroSemigroup

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, ZeroSemigroup a) => (x -> a) -> GlobalFailure x -> a

FreeRBPM ListUnfold SkewedAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, SkewedAlgebra a) => (x -> a) -> ListUnfold x -> a

FreeRBPM MazeWalk PalindromeAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, PalindromeAlgebra a) => (x -> a) -> MazeWalk x -> a

FreeRBPM [] Monoid

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, Monoid a) => (x -> a) -> [x] -> a

KnownNat n => FreeRBPM (Stutter n) (StutterAlgebra n)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterAlgebra n a) => (x -> a) -> Stutter n x -> a

KnownNat n => FreeRBPM (StutterKeeper n) (StutterKeeperAlgebra n)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterKeeperAlgebra n a) => (x -> a) -> StutterKeeper n x -> a

(KnownNat n, KnownNat m) => FreeRBPM (StutterStutter n m) (StutterStutterAlgebra n m)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterStutterAlgebra n m a) => (x -> a) -> StutterStutter n m x -> a

The Global Failure monad

class PointedMagma a => ZeroSemigroup a

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

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, ZeroSemigroup a) => (x -> a) -> GlobalFailure x -> a

ZeroSemigroup (GlobalFailure a)

Defined in Control.Monad.List.Exotic

newtype GlobalFailure a

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 []

Constructors

GlobalFailure

Fields

• unGlobalFailure :: [a]

Instances

Applicative GlobalFailure

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> GlobalFailure a

(<*>) :: GlobalFailure (a -> b) -> GlobalFailure a -> GlobalFailure b

liftA2 :: (a -> b -> c) -> GlobalFailure a -> GlobalFailure b -> GlobalFailure c

(*>) :: GlobalFailure a -> GlobalFailure b -> GlobalFailure b

(<*) :: GlobalFailure a -> GlobalFailure b -> GlobalFailure a

Functor GlobalFailure

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> GlobalFailure a -> GlobalFailure b

(<$) :: a -> GlobalFailure b -> GlobalFailure a

Monad GlobalFailure

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: GlobalFailure a -> (a -> GlobalFailure b) -> GlobalFailure b

(>>) :: GlobalFailure a -> GlobalFailure b -> GlobalFailure b

return :: a -> GlobalFailure a

ListMonad GlobalFailure

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> GlobalFailure a

unwrap :: GlobalFailure a -> [a]

FreeRBPM GlobalFailure ZeroSemigroup

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, ZeroSemigroup a) => (x -> a) -> GlobalFailure x -> a

IsString (GlobalFailure Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> GlobalFailure Char

IsList (GlobalFailure a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (GlobalFailure a)

Methods

fromList :: [Item (GlobalFailure a)] -> GlobalFailure a

fromListN :: Int -> [Item (GlobalFailure a)] -> GlobalFailure a

toList :: GlobalFailure a -> [Item (GlobalFailure a)]

Show a => Show (GlobalFailure a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> GlobalFailure a -> ShowS

show :: GlobalFailure a -> String

showList :: [GlobalFailure a] -> ShowS

PointedMagma (GlobalFailure a)

Defined in Control.Monad.List.Exotic

Methods

eps :: GlobalFailure a

(<>) :: GlobalFailure a -> GlobalFailure a -> GlobalFailure a

ZeroSemigroup (GlobalFailure a)

Defined in Control.Monad.List.Exotic

Eq a => Eq (GlobalFailure a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: GlobalFailure a -> GlobalFailure a -> Bool

(/=) :: GlobalFailure a -> GlobalFailure a -> Bool

type Item (GlobalFailure a)

Defined in Control.Monad.List.Exotic

type Item (GlobalFailure a) = a

The Maze Walk monad

class PointedMagma a => PalindromeAlgebra a

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

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, PalindromeAlgebra a) => (x -> a) -> MazeWalk x -> a

PalindromeAlgebra (MazeWalk a)

Defined in Control.Monad.List.Exotic

palindromize :: [a] -> [a]

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

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

newtype MazeWalk a

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).

Constructors

MazeWalk

Fields

• unMazeWalk :: [a]

Instances

Applicative MazeWalk

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> MazeWalk a

(<*>) :: MazeWalk (a -> b) -> MazeWalk a -> MazeWalk b

liftA2 :: (a -> b -> c) -> MazeWalk a -> MazeWalk b -> MazeWalk c

(*>) :: MazeWalk a -> MazeWalk b -> MazeWalk b

(<*) :: MazeWalk a -> MazeWalk b -> MazeWalk a

Functor MazeWalk

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> MazeWalk a -> MazeWalk b

(<$) :: a -> MazeWalk b -> MazeWalk a

Monad MazeWalk

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: MazeWalk a -> (a -> MazeWalk b) -> MazeWalk b

(>>) :: MazeWalk a -> MazeWalk b -> MazeWalk b

return :: a -> MazeWalk a

ListMonad MazeWalk

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> MazeWalk a

unwrap :: MazeWalk a -> [a]

FreeRBPM MazeWalk PalindromeAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, PalindromeAlgebra a) => (x -> a) -> MazeWalk x -> a

IsString (MazeWalk Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> MazeWalk Char

IsList (MazeWalk a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (MazeWalk a)

Methods

fromList :: [Item (MazeWalk a)] -> MazeWalk a

fromListN :: Int -> [Item (MazeWalk a)] -> MazeWalk a

toList :: MazeWalk a -> [Item (MazeWalk a)]

Show a => Show (MazeWalk a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> MazeWalk a -> ShowS

show :: MazeWalk a -> String

showList :: [MazeWalk a] -> ShowS

PalindromeAlgebra (MazeWalk a)

Defined in Control.Monad.List.Exotic

PointedMagma (MazeWalk a)

Defined in Control.Monad.List.Exotic

Methods

eps :: MazeWalk a

(<>) :: MazeWalk a -> MazeWalk a -> MazeWalk a

Eq a => Eq (MazeWalk a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: MazeWalk a -> MazeWalk a -> Bool

(/=) :: MazeWalk a -> MazeWalk a -> Bool

type Item (MazeWalk a)

Defined in Control.Monad.List.Exotic

type Item (MazeWalk a) = a

The Discrete Hybrid monad

class PointedMagma a => LeaningAlgebra a

Instances should satisfy the following:

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

Instances

FreeRBPM DiscreteHybrid LeaningAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, LeaningAlgebra a) => (x -> a) -> DiscreteHybrid x -> a

LeaningAlgebra (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

safeLast :: [a] -> [a]

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

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

newtype DiscreteHybrid a

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"

Constructors

DiscreteHybrid

Fields

• unDiscreteHybrid :: [a]

Instances

Applicative DiscreteHybrid

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> DiscreteHybrid a

(<*>) :: DiscreteHybrid (a -> b) -> DiscreteHybrid a -> DiscreteHybrid b

liftA2 :: (a -> b -> c) -> DiscreteHybrid a -> DiscreteHybrid b -> DiscreteHybrid c

(*>) :: DiscreteHybrid a -> DiscreteHybrid b -> DiscreteHybrid b

(<*) :: DiscreteHybrid a -> DiscreteHybrid b -> DiscreteHybrid a

Functor DiscreteHybrid

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> DiscreteHybrid a -> DiscreteHybrid b

(<$) :: a -> DiscreteHybrid b -> DiscreteHybrid a

Monad DiscreteHybrid

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: DiscreteHybrid a -> (a -> DiscreteHybrid b) -> DiscreteHybrid b

(>>) :: DiscreteHybrid a -> DiscreteHybrid b -> DiscreteHybrid b

return :: a -> DiscreteHybrid a

ListMonad DiscreteHybrid

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> DiscreteHybrid a

unwrap :: DiscreteHybrid a -> [a]

FreeRBPM DiscreteHybrid LeaningAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, LeaningAlgebra a) => (x -> a) -> DiscreteHybrid x -> a

IsString (DiscreteHybrid Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> DiscreteHybrid Char

IsList (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (DiscreteHybrid a)

Methods

fromList :: [Item (DiscreteHybrid a)] -> DiscreteHybrid a

fromListN :: Int -> [Item (DiscreteHybrid a)] -> DiscreteHybrid a

toList :: DiscreteHybrid a -> [Item (DiscreteHybrid a)]

Show a => Show (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> DiscreteHybrid a -> ShowS

show :: DiscreteHybrid a -> String

showList :: [DiscreteHybrid a] -> ShowS

LeaningAlgebra (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

PointedMagma (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

Methods

eps :: DiscreteHybrid a

(<>) :: DiscreteHybrid a -> DiscreteHybrid a -> DiscreteHybrid a

Eq a => Eq (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: DiscreteHybrid a -> DiscreteHybrid a -> Bool

(/=) :: DiscreteHybrid a -> DiscreteHybrid a -> Bool

type Item (DiscreteHybrid a)

Defined in Control.Monad.List.Exotic

type Item (DiscreteHybrid a) = a

The List Unfold monad

class PointedMagma a => SkewedAlgebra a

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

Instances

FreeRBPM ListUnfold SkewedAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, SkewedAlgebra a) => (x -> a) -> ListUnfold x -> a

SkewedAlgebra (ListUnfold a)

Defined in Control.Monad.List.Exotic

newtype ListUnfold a

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 []

Constructors

ListUnfold

Fields

• unListUnfold :: [a]

Instances

Applicative ListUnfold

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> ListUnfold a

(<*>) :: ListUnfold (a -> b) -> ListUnfold a -> ListUnfold b

liftA2 :: (a -> b -> c) -> ListUnfold a -> ListUnfold b -> ListUnfold c

(*>) :: ListUnfold a -> ListUnfold b -> ListUnfold b

(<*) :: ListUnfold a -> ListUnfold b -> ListUnfold a

Functor ListUnfold

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> ListUnfold a -> ListUnfold b

(<$) :: a -> ListUnfold b -> ListUnfold a

Monad ListUnfold

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: ListUnfold a -> (a -> ListUnfold b) -> ListUnfold b

(>>) :: ListUnfold a -> ListUnfold b -> ListUnfold b

return :: a -> ListUnfold a

ListMonad ListUnfold

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> ListUnfold a

unwrap :: ListUnfold a -> [a]

FreeRBPM ListUnfold SkewedAlgebra

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, SkewedAlgebra a) => (x -> a) -> ListUnfold x -> a

IsString (ListUnfold Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> ListUnfold Char

IsList (ListUnfold a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (ListUnfold a)

Methods

fromList :: [Item (ListUnfold a)] -> ListUnfold a

fromListN :: Int -> [Item (ListUnfold a)] -> ListUnfold a

toList :: ListUnfold a -> [Item (ListUnfold a)]

Show a => Show (ListUnfold a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> ListUnfold a -> ShowS

show :: ListUnfold a -> String

showList :: [ListUnfold a] -> ShowS

PointedMagma (ListUnfold a)

Defined in Control.Monad.List.Exotic

Methods

eps :: ListUnfold a

(<>) :: ListUnfold a -> ListUnfold a -> ListUnfold a

SkewedAlgebra (ListUnfold a)

Defined in Control.Monad.List.Exotic

Eq a => Eq (ListUnfold a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: ListUnfold a -> ListUnfold a -> Bool

(/=) :: ListUnfold a -> ListUnfold a -> Bool

type Item (ListUnfold a)

Defined in Control.Monad.List.Exotic

type Item (ListUnfold a) = a

The Stutter monad

class (KnownNat n, PointedMagma a) => StutterAlgebra n a

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)

Defined in Control.Monad.List.Exotic

KnownNat n => FreeRBPM (Stutter n) (StutterAlgebra n)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterAlgebra n a) => (x -> a) -> Stutter n x -> a

replicateLast :: Int -> [a] -> [a]

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

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 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"

Constructors

Stutter

Fields

• unStutter :: [a]

Instances

KnownNat n => StutterAlgebra n (Stutter n a)

Defined in Control.Monad.List.Exotic

KnownNat n => Applicative (Stutter n)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> Stutter n a

(<*>) :: Stutter n (a -> b) -> Stutter n a -> Stutter n b

liftA2 :: (a -> b -> c) -> Stutter n a -> Stutter n b -> Stutter n c

(*>) :: Stutter n a -> Stutter n b -> Stutter n b

(<*) :: Stutter n a -> Stutter n b -> Stutter n a

Functor (Stutter n)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> Stutter n a -> Stutter n b

(<$) :: a -> Stutter n b -> Stutter n a

KnownNat n => Monad (Stutter n)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: Stutter n a -> (a -> Stutter n b) -> Stutter n b

(>>) :: Stutter n a -> Stutter n b -> Stutter n b

return :: a -> Stutter n a

KnownNat n => ListMonad (Stutter n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> Stutter n a

unwrap :: Stutter n a -> [a]

KnownNat n => FreeRBPM (Stutter n) (StutterAlgebra n)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterAlgebra n a) => (x -> a) -> Stutter n x -> a

KnownNat n => IsString (Stutter n Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> Stutter n Char

KnownNat n => IsList (Stutter n a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (Stutter n a)

Methods

fromList :: [Item (Stutter n a)] -> Stutter n a

fromListN :: Int -> [Item (Stutter n a)] -> Stutter n a

toList :: Stutter n a -> [Item (Stutter n a)]

Show a => Show (Stutter n a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> Stutter n a -> ShowS

show :: Stutter n a -> String

showList :: [Stutter n a] -> ShowS

KnownNat n => PointedMagma (Stutter n a)

Defined in Control.Monad.List.Exotic

Methods

eps :: Stutter n a

(<>) :: Stutter n a -> Stutter n a -> Stutter n a

Eq a => Eq (Stutter n a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: Stutter n a -> Stutter n a -> Bool

(/=) :: Stutter n a -> Stutter n a -> Bool

type Item (Stutter n a)

Defined in Control.Monad.List.Exotic

type Item (Stutter n a) = a

The Stutter-Keeper monad

class (KnownNat n, PointedMagma a) => StutterKeeperAlgebra n a

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

Instances

KnownNat n => StutterKeeperAlgebra n (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

KnownNat n => FreeRBPM (StutterKeeper n) (StutterKeeperAlgebra n)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterKeeperAlgebra n a) => (x -> a) -> StutterKeeper n x -> a

newtype StutterKeeper (n :: Nat) a

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
         = []
         | 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"

Constructors

StutterKeeper

Fields

• unStutterKeeper :: [a]

Instances

KnownNat n => StutterKeeperAlgebra n (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

KnownNat n => Applicative (StutterKeeper n)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> StutterKeeper n a

(<*>) :: StutterKeeper n (a -> b) -> StutterKeeper n a -> StutterKeeper n b

liftA2 :: (a -> b -> c) -> StutterKeeper n a -> StutterKeeper n b -> StutterKeeper n c

(*>) :: StutterKeeper n a -> StutterKeeper n b -> StutterKeeper n b

(<*) :: StutterKeeper n a -> StutterKeeper n b -> StutterKeeper n a

Functor (StutterKeeper n)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> StutterKeeper n a -> StutterKeeper n b

(<$) :: a -> StutterKeeper n b -> StutterKeeper n a

KnownNat n => Monad (StutterKeeper n)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: StutterKeeper n a -> (a -> StutterKeeper n b) -> StutterKeeper n b

(>>) :: StutterKeeper n a -> StutterKeeper n b -> StutterKeeper n b

return :: a -> StutterKeeper n a

KnownNat n => ListMonad (StutterKeeper n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> StutterKeeper n a

unwrap :: StutterKeeper n a -> [a]

KnownNat n => FreeRBPM (StutterKeeper n) (StutterKeeperAlgebra n)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterKeeperAlgebra n a) => (x -> a) -> StutterKeeper n x -> a

KnownNat n => IsString (StutterKeeper n Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> StutterKeeper n Char

KnownNat n => IsList (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (StutterKeeper n a)

Methods

fromList :: [Item (StutterKeeper n a)] -> StutterKeeper n a

fromListN :: Int -> [Item (StutterKeeper n a)] -> StutterKeeper n a

toList :: StutterKeeper n a -> [Item (StutterKeeper n a)]

Show a => Show (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> StutterKeeper n a -> ShowS

show :: StutterKeeper n a -> String

showList :: [StutterKeeper n a] -> ShowS

KnownNat n => PointedMagma (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

Methods

eps :: StutterKeeper n a

(<>) :: StutterKeeper n a -> StutterKeeper n a -> StutterKeeper n a

Eq a => Eq (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: StutterKeeper n a -> StutterKeeper n a -> Bool

(/=) :: StutterKeeper n a -> StutterKeeper n a -> Bool

type Item (StutterKeeper n a)

Defined in Control.Monad.List.Exotic

type Item (StutterKeeper n a) = a

The Stutter-Stutter monad

class (KnownNat n, KnownNat m, PointedMagma a) => StutterStutterAlgebra n m a

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)

Instances

(KnownNat n, KnownNat m) => StutterStutterAlgebra n m (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

(KnownNat n, KnownNat m) => FreeRBPM (StutterStutter n m) (StutterStutterAlgebra n m)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterStutterAlgebra n m a) => (x -> a) -> StutterStutter n m x -> a

newtype StutterStutter (n :: Nat) (m :: Nat) 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
         = []
         | 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"

Constructors

StutterStutter

Fields

• unStutterStutter :: [a]

Instances

(KnownNat n, KnownNat m) => StutterStutterAlgebra n m (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

(KnownNat n, KnownNat m) => Applicative (StutterStutter n m)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> StutterStutter n m a

(<*>) :: StutterStutter n m (a -> b) -> StutterStutter n m a -> StutterStutter n m b

liftA2 :: (a -> b -> c) -> StutterStutter n m a -> StutterStutter n m b -> StutterStutter n m c

(*>) :: StutterStutter n m a -> StutterStutter n m b -> StutterStutter n m b

(<*) :: StutterStutter n m a -> StutterStutter n m b -> StutterStutter n m a

Functor (StutterStutter n m)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> StutterStutter n m a -> StutterStutter n m b

(<$) :: a -> StutterStutter n m b -> StutterStutter n m a

(KnownNat n, KnownNat m) => Monad (StutterStutter n m)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: StutterStutter n m a -> (a -> StutterStutter n m b) -> StutterStutter n m b

(>>) :: StutterStutter n m a -> StutterStutter n m b -> StutterStutter n m b

return :: a -> StutterStutter n m a

(KnownNat n, KnownNat m) => ListMonad (StutterStutter n m)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> StutterStutter n m a

unwrap :: StutterStutter n m a -> [a]

(KnownNat n, KnownNat m) => FreeRBPM (StutterStutter n m) (StutterStutterAlgebra n m)

Defined in Control.Monad.List.Exotic

Methods

foldRBPM :: (PointedMagma a, StutterStutterAlgebra n m a) => (x -> a) -> StutterStutter n m x -> a

(KnownNat n, KnownNat m) => IsString (StutterStutter n m Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> StutterStutter n m Char

(KnownNat n, KnownNat m) => IsList (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (StutterStutter n m a)

Methods

fromList :: [Item (StutterStutter n m a)] -> StutterStutter n m a

fromListN :: Int -> [Item (StutterStutter n m a)] -> StutterStutter n m a

toList :: StutterStutter n m a -> [Item (StutterStutter n m a)]

Show a => Show (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> StutterStutter n m a -> ShowS

show :: StutterStutter n m a -> String

showList :: [StutterStutter n m a] -> ShowS

(KnownNat n, KnownNat m) => PointedMagma (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

Methods

eps :: StutterStutter n m a

(<>) :: StutterStutter n m a -> StutterStutter n m a -> StutterStutter n m a

Eq a => Eq (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: StutterStutter n m a -> StutterStutter n m a -> Bool

(/=) :: StutterStutter n m a -> StutterStutter n m a -> Bool

type Item (StutterStutter n m a)

Defined in Control.Monad.List.Exotic

type Item (StutterStutter n m a) = a

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 \ |\ x-1 \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 non-accepted 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

newtype Mini a

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).

Constructors

Mini

Fields

• unMini :: [a]

Instances

Applicative Mini

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> Mini a

(<*>) :: Mini (a -> b) -> Mini a -> Mini b

liftA2 :: (a -> b -> c) -> Mini a -> Mini b -> Mini c

(*>) :: Mini a -> Mini b -> Mini b

(<*) :: Mini a -> Mini b -> Mini a

Functor Mini

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> Mini a -> Mini b

(<$) :: a -> Mini b -> Mini a

Monad Mini

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: Mini a -> (a -> Mini b) -> Mini b

(>>) :: Mini a -> Mini b -> Mini b

return :: a -> Mini a

ListMonad Mini

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> Mini a

unwrap :: Mini a -> [a]

IsString (Mini Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> Mini Char

IsList (Mini a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (Mini a)

Methods

fromList :: [Item (Mini a)] -> Mini a

fromListN :: Int -> [Item (Mini a)] -> Mini a

toList :: Mini a -> [Item (Mini a)]

Show a => Show (Mini a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> Mini a -> ShowS

show :: Mini a -> String

showList :: [Mini a] -> ShowS

Eq a => Eq (Mini a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: Mini a -> Mini a -> Bool

(/=) :: Mini a -> Mini a -> Bool

type Item (Mini a)

Defined in Control.Monad.List.Exotic

type Item (Mini a) = a

The Odd monad

newtype Odd a

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.

Constructors

Odd

Fields

• unOdd :: [a]

Instances

Applicative Odd

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> Odd a

(<*>) :: Odd (a -> b) -> Odd a -> Odd b

liftA2 :: (a -> b -> c) -> Odd a -> Odd b -> Odd c

(*>) :: Odd a -> Odd b -> Odd b

(<*) :: Odd a -> Odd b -> Odd a

Functor Odd

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> Odd a -> Odd b

(<$) :: a -> Odd b -> Odd a

Monad Odd

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: Odd a -> (a -> Odd b) -> Odd b

(>>) :: Odd a -> Odd b -> Odd b

return :: a -> Odd a

ListMonad Odd

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> Odd a

unwrap :: Odd a -> [a]

IsString (Odd Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> Odd Char

IsList (Odd a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (Odd a)

Methods

fromList :: [Item (Odd a)] -> Odd a

fromListN :: Int -> [Item (Odd a)] -> Odd a

toList :: Odd a -> [Item (Odd a)]

Show a => Show (Odd a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> Odd a -> ShowS

show :: Odd a -> String

showList :: [Odd a] -> ShowS

Eq a => Eq (Odd a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: Odd a -> Odd a -> Bool

(/=) :: Odd a -> Odd a -> Bool

type Item (Odd a)

Defined in Control.Monad.List.Exotic

type Item (Odd a) = a

The At Least monad

newtype AtLeast (n :: Nat) a

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\}\).

Constructors

AtLeast

Fields

• unAtLeast :: [a]

Instances

KnownNat n => Applicative (AtLeast n)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> AtLeast n a

(<*>) :: AtLeast n (a -> b) -> AtLeast n a -> AtLeast n b

liftA2 :: (a -> b -> c) -> AtLeast n a -> AtLeast n b -> AtLeast n c

(*>) :: AtLeast n a -> AtLeast n b -> AtLeast n b

(<*) :: AtLeast n a -> AtLeast n b -> AtLeast n a

Functor (AtLeast n)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> AtLeast n a -> AtLeast n b

(<$) :: a -> AtLeast n b -> AtLeast n a

KnownNat n => Monad (AtLeast n)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: AtLeast n a -> (a -> AtLeast n b) -> AtLeast n b

(>>) :: AtLeast n a -> AtLeast n b -> AtLeast n b

return :: a -> AtLeast n a

KnownNat n => ListMonad (AtLeast n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> AtLeast n a

unwrap :: AtLeast n a -> [a]

KnownNat n => IsString (AtLeast n Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> AtLeast n Char

KnownNat n => IsList (AtLeast n a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (AtLeast n a)

Methods

fromList :: [Item (AtLeast n a)] -> AtLeast n a

fromListN :: Int -> [Item (AtLeast n a)] -> AtLeast n a

toList :: AtLeast n a -> [Item (AtLeast n a)]

Show a => Show (AtLeast n a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> AtLeast n a -> ShowS

show :: AtLeast n a -> String

showList :: [AtLeast n a] -> ShowS

Eq a => Eq (AtLeast n a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: AtLeast n a -> AtLeast n a -> Bool

(/=) :: AtLeast n a -> AtLeast n a -> Bool

type Item (AtLeast n a)

Defined in Control.Monad.List.Exotic

type Item (AtLeast n a) = a

The Numerical Monoid monad

class NumericalMonoidGenerators (ns :: [Nat]) where

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.

Methods

isInNumericalMonoid :: Int -> Bool

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])

Defined in Control.Monad.List.Exotic

Methods

isInNumericalMonoid :: Int -> Bool

(KnownNat g, NumericalMonoidGenerators gs) => NumericalMonoidGenerators (g ': gs)

Defined in Control.Monad.List.Exotic

Methods

isInNumericalMonoid :: Int -> Bool

newtype NumericalMonoidMonad (ns :: [Nat]) a

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].

Constructors

NumericalMonoidMonad

Fields

• unNumericalMonoidMonad :: [a]

Instances

NumericalMonoidGenerators ns => Applicative (NumericalMonoidMonad ns)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> NumericalMonoidMonad ns a

(<*>) :: NumericalMonoidMonad ns (a -> b) -> NumericalMonoidMonad ns a -> NumericalMonoidMonad ns b

liftA2 :: (a -> b -> c) -> NumericalMonoidMonad ns a -> NumericalMonoidMonad ns b -> NumericalMonoidMonad ns c

(*>) :: NumericalMonoidMonad ns a -> NumericalMonoidMonad ns b -> NumericalMonoidMonad ns b

(<*) :: NumericalMonoidMonad ns a -> NumericalMonoidMonad ns b -> NumericalMonoidMonad ns a

Functor (NumericalMonoidMonad ns)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> NumericalMonoidMonad ns a -> NumericalMonoidMonad ns b

(<$) :: a -> NumericalMonoidMonad ns b -> NumericalMonoidMonad ns a

NumericalMonoidGenerators ns => Monad (NumericalMonoidMonad ns)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: NumericalMonoidMonad ns a -> (a -> NumericalMonoidMonad ns b) -> NumericalMonoidMonad ns b

(>>) :: NumericalMonoidMonad ns a -> NumericalMonoidMonad ns b -> NumericalMonoidMonad ns b

return :: a -> NumericalMonoidMonad ns a

NumericalMonoidGenerators ns => ListMonad (NumericalMonoidMonad ns)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> NumericalMonoidMonad ns a

unwrap :: NumericalMonoidMonad ns a -> [a]

IsString (NumericalMonoidMonad ns Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> NumericalMonoidMonad ns Char

IsList (NumericalMonoidMonad ns a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (NumericalMonoidMonad ns a)

Methods

fromList :: [Item (NumericalMonoidMonad ns a)] -> NumericalMonoidMonad ns a

fromListN :: Int -> [Item (NumericalMonoidMonad ns a)] -> NumericalMonoidMonad ns a

toList :: NumericalMonoidMonad ns a -> [Item (NumericalMonoidMonad ns a)]

Show a => Show (NumericalMonoidMonad ns a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> NumericalMonoidMonad ns a -> ShowS

show :: NumericalMonoidMonad ns a -> String

showList :: [NumericalMonoidMonad ns a] -> ShowS

Eq a => Eq (NumericalMonoidMonad ns a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: NumericalMonoidMonad ns a -> NumericalMonoidMonad ns a -> Bool

(/=) :: NumericalMonoidMonad ns a -> NumericalMonoidMonad ns a -> Bool

type Item (NumericalMonoidMonad ns a)

Defined in Control.Monad.List.Exotic

type Item (NumericalMonoidMonad ns a) = a

Other list monads

The At Most monad

newtype AtMost (n :: Nat) a

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 ""

Constructors

AtMost

Fields

• unAtMost :: [a]

Instances

KnownNat n => Applicative (AtMost n)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> AtMost n a

(<*>) :: AtMost n (a -> b) -> AtMost n a -> AtMost n b

liftA2 :: (a -> b -> c) -> AtMost n a -> AtMost n b -> AtMost n c

(*>) :: AtMost n a -> AtMost n b -> AtMost n b

(<*) :: AtMost n a -> AtMost n b -> AtMost n a

Functor (AtMost n)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> AtMost n a -> AtMost n b

(<$) :: a -> AtMost n b -> AtMost n a

KnownNat n => Monad (AtMost n)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: AtMost n a -> (a -> AtMost n b) -> AtMost n b

(>>) :: AtMost n a -> AtMost n b -> AtMost n b

return :: a -> AtMost n a

KnownNat n => ListMonad (AtMost n)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> AtMost n a

unwrap :: AtMost n a -> [a]

KnownNat n => IsString (AtMost n Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> AtMost n Char

KnownNat n => IsList (AtMost n a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (AtMost n a)

Methods

fromList :: [Item (AtMost n a)] -> AtMost n a

fromListN :: Int -> [Item (AtMost n a)] -> AtMost n a

toList :: AtMost n a -> [Item (AtMost n a)]

Show a => Show (AtMost n a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> AtMost n a -> ShowS

show :: AtMost n a -> String

showList :: [AtMost n a] -> ShowS

Eq a => Eq (AtMost n a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: AtMost n a -> AtMost n a -> Bool

(/=) :: AtMost n a -> AtMost n a -> Bool

type Item (AtMost n a)

Defined in Control.Monad.List.Exotic

type Item (AtMost n a) = a

The Continuum-of-Monads 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 ContinuumOfMonads, which is parameterised by a subset of the set of natural numbers (SetOfNats).

class SetOfNats (a :: Symbol) where

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]

Methods

elemOf :: Int -> Bool

The characteristic function of the defined set.

Instances

SetOfNats "Fib"

The set of Fibonacci numbers.

Defined in Control.Monad.List.Exotic

Methods

elemOf :: Int -> Bool

SetOfNats "Primes"

The set of prime numbers.

Defined in Control.Monad.List.Exotic

Methods

elemOf :: Int -> Bool

newtype ContinuumOfMonads (s :: Symbol) a

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 []

Constructors

ContinuumOfMonads

Fields

• unContinuumOfMonads :: [a]

Instances

SetOfNats s => Applicative (ContinuumOfMonads s)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> ContinuumOfMonads s a

(<*>) :: ContinuumOfMonads s (a -> b) -> ContinuumOfMonads s a -> ContinuumOfMonads s b

liftA2 :: (a -> b -> c) -> ContinuumOfMonads s a -> ContinuumOfMonads s b -> ContinuumOfMonads s c

(*>) :: ContinuumOfMonads s a -> ContinuumOfMonads s b -> ContinuumOfMonads s b

(<*) :: ContinuumOfMonads s a -> ContinuumOfMonads s b -> ContinuumOfMonads s a

Functor (ContinuumOfMonads s)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> ContinuumOfMonads s a -> ContinuumOfMonads s b

(<$) :: a -> ContinuumOfMonads s b -> ContinuumOfMonads s a

SetOfNats s => Monad (ContinuumOfMonads s)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: ContinuumOfMonads s a -> (a -> ContinuumOfMonads s b) -> ContinuumOfMonads s b

(>>) :: ContinuumOfMonads s a -> ContinuumOfMonads s b -> ContinuumOfMonads s b

return :: a -> ContinuumOfMonads s a

SetOfNats s => ListMonad (ContinuumOfMonads s)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> ContinuumOfMonads s a

unwrap :: ContinuumOfMonads s a -> [a]

IsString (ContinuumOfMonads s Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> ContinuumOfMonads s Char

IsList (ContinuumOfMonads s a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (ContinuumOfMonads s a)

Methods

fromList :: [Item (ContinuumOfMonads s a)] -> ContinuumOfMonads s a

fromListN :: Int -> [Item (ContinuumOfMonads s a)] -> ContinuumOfMonads s a

toList :: ContinuumOfMonads s a -> [Item (ContinuumOfMonads s a)]

Show a => Show (ContinuumOfMonads s a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> ContinuumOfMonads s a -> ShowS

show :: ContinuumOfMonads s a -> String

showList :: [ContinuumOfMonads s a] -> ShowS

Eq a => Eq (ContinuumOfMonads s a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: ContinuumOfMonads s a -> ContinuumOfMonads s a -> Bool

(/=) :: ContinuumOfMonads s a -> ContinuumOfMonads s a -> Bool

type Item (ContinuumOfMonads s a)

Defined in Control.Monad.List.Exotic

type Item (ContinuumOfMonads s a) = a

The Short Stutter-Keeper monad (?)

newtype ShortStutterKeeper (n :: Nat) (p :: Nat) a

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.

Constructors

ShortStutterKeeper

Fields

• unShortStutterKeeper :: [a]

Instances

(KnownNat n, KnownNat p) => Applicative (ShortStutterKeeper n p)

Defined in Control.Monad.List.Exotic

Methods

pure :: a -> ShortStutterKeeper n p a

(<*>) :: ShortStutterKeeper n p (a -> b) -> ShortStutterKeeper n p a -> ShortStutterKeeper n p b

liftA2 :: (a -> b -> c) -> ShortStutterKeeper n p a -> ShortStutterKeeper n p b -> ShortStutterKeeper n p c

(*>) :: ShortStutterKeeper n p a -> ShortStutterKeeper n p b -> ShortStutterKeeper n p b

(<*) :: ShortStutterKeeper n p a -> ShortStutterKeeper n p b -> ShortStutterKeeper n p a

Functor (ShortStutterKeeper n p)

Defined in Control.Monad.List.Exotic

Methods

fmap :: (a -> b) -> ShortStutterKeeper n p a -> ShortStutterKeeper n p b

(<$) :: a -> ShortStutterKeeper n p b -> ShortStutterKeeper n p a

(KnownNat n, KnownNat p) => Monad (ShortStutterKeeper n p)

Defined in Control.Monad.List.Exotic

Methods

(>>=) :: ShortStutterKeeper n p a -> (a -> ShortStutterKeeper n p b) -> ShortStutterKeeper n p b

(>>) :: ShortStutterKeeper n p a -> ShortStutterKeeper n p b -> ShortStutterKeeper n p b

return :: a -> ShortStutterKeeper n p a

(KnownNat n, KnownNat p) => ListMonad (ShortStutterKeeper n p)

Defined in Control.Monad.List.Exotic

Methods

wrap :: [a] -> ShortStutterKeeper n p a

unwrap :: ShortStutterKeeper n p a -> [a]

(KnownNat n, KnownNat p) => IsString (ShortStutterKeeper n p Char)

Defined in Control.Monad.List.Exotic

Methods

fromString :: String -> ShortStutterKeeper n p Char

(KnownNat n, KnownNat p) => IsList (ShortStutterKeeper n p a)

Defined in Control.Monad.List.Exotic

Associated Types

type Item (ShortStutterKeeper n p a)

Methods

fromList :: [Item (ShortStutterKeeper n p a)] -> ShortStutterKeeper n p a

fromListN :: Int -> [Item (ShortStutterKeeper n p a)] -> ShortStutterKeeper n p a

toList :: ShortStutterKeeper n p a -> [Item (ShortStutterKeeper n p a)]

Show a => Show (ShortStutterKeeper n p a)

Defined in Control.Monad.List.Exotic

Methods

showsPrec :: Int -> ShortStutterKeeper n p a -> ShowS

show :: ShortStutterKeeper n p a -> String

showList :: [ShortStutterKeeper n p a] -> ShowS

Eq a => Eq (ShortStutterKeeper n p a)

Defined in Control.Monad.List.Exotic

Methods

(==) :: ShortStutterKeeper n p a -> ShortStutterKeeper n p a -> Bool

(/=) :: ShortStutterKeeper n p a -> ShortStutterKeeper n p a -> Bool

type Item (ShortStutterKeeper n p a)

Defined in Control.Monad.List.Exotic

type Item (ShortStutterKeeper n p a) = a