Lawful list and set monad transformers based on free monads.

This package provides a lawful ListT implementation based on free monads. It also provides an _Applicative_ list transformer, which is a lawful Applicative, and isomorphic to the old ListT.

Free ListT

This package provides a lawful ListT implementation based on free monads. It also provides an Applicative list transformer, which is a lawful Applicative, and isomorphic to the old ListT.

Background

The old ListT transformer from transformers < 0.6 was unlawful: For a noncommutative monad, ListT m was not a monad. It was implemented simply as the composition of list and m:

newtype ListT m a = ListT (m [a])

As such, it is automatically a lawful Functor and Applicative in a canonical way. But famously, a composition of two monads is not always a monad, and in this case, it in fact isn't.

Previous approaches

Streaming

There is one popular approach to ListT, representing the transformer as a stream:

newtype ListT m a = ListT (m (Maybe (a, ListT m a)))

This approach is implemented in https://hackage.haskell.org/package/list-t and https://hackage.haskell.org/package/list-transformer, and it is a great choice in many cases.

Basically, to go through the list, one has to perform one effect in m at each step, and one discovers whether the list now ends or produces a further element. But this also means that the list structure enforces all earlier m effects before a later element can be accessed.

Church-encoding

Another possibility is Church-encoding the list, which is implemented in logict.

Free approach

A simple algebraic approach that does not enforce the linear structure of streaming ListT is a free monad:

newtype ListT m a = ListT (FreeT [] m a)

This gives a branching rose tree of computations, where at every step in m, arbitrarily many branches can arise.

Unfolding the definition of FreeT as an algebraic datatype would result in something like:

data ListT m a = OneLayer (m a) | TwoLayers (m [m a]) | ThreeLayers (m [m [m a]]) | ...

Applicative transformer

As mentioned already, the old ListT is a valid Applicative transformer, which means that ListT m is a lawful Applicative as long as m is. This is useful and sufficient in many situations, which is why it is reinstated here.

Also, values of type m [a] occur very often in the wild (for example when using mapM), so it makes sense to give them a proper type that captures their properties.

To give some more examples, all lawful ListT implementations have some kind of "running" function that maps it to m [a]. The free ListT is no exception here. In a sense, one can "flatten" or "concatenate" all free list layers into a single one. While this is a natural transformation, this is of course not a monad morphism.