free-listt: Lawful list and set monad transformers based on free monads

[ control, library, mit ] [ Propose Tags ] [ Report a vulnerability ]

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.


[Skip to Readme]

Modules

[Index] [Quick Jump]

Flags

Manual Flags

NameDescriptionDefault
dev

Enable warnings as errors. Active on ci.

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0, 0.1.0.1
Change log CHANGELOG.md
Dependencies base (>=4.14.3.0 && <4.20), exceptions (>=0.10 && <0.11), free (>=5.1.3 && <5.3), mtl (>=2.3 && <2.4), transformers (>=0.6 && <0.7) [details]
Tested with ghc ==8.10.7, ghc ==9.0.2, ghc ==9.2.8, ghc ==9.4.8, ghc ==9.6.3, ghc ==9.8.1
License MIT
Author Manuel Bärenz
Maintainer programming@manuelbaerenz.de
Category Control
Source repo head: git clone https://github.com/turion/free-listt.git
Uploaded by turion at 2024-01-03T16:34:46Z
Distributions NixOS:0.1.0.1
Downloads 88 total (4 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-01-03 [all 1 reports]

Readme for free-listt-0.1.0.1

[back to package description]

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.