free-listt 0.1.0.0 → 0.1.0.1

raw patch · 3 files changed

+75/−3 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +2/−2
• README.md +71/−0
• free-listt.cabal +2/−1

@@ -1,5 +1,5 @@ # Revision history for free-listt -## 0.1.0.0 -- YYYY-mm-dd+## 0.1.0.0 -- 2024-01-03 -* First version. Released on an unsuspecting world.+* Provide free `ListT` and `Applicative` `ListT` transformers

@@ -0,0 +1,71 @@+# 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`](https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-List.html) was unlawful:+For a noncommutative monad, `ListT m` was not a monad.+It was implemented simply as the composition of list and `m`:++```haskell+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:++```haskell+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`](https://hackage.haskell.org/package/logict).++### Free approach++A simple algebraic approach that does not enforce the linear structure of streaming `ListT` is a free monad:++```haskell+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:++```haskell+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`](https://hackage.haskell.org/package/base-4.19.0.0/docs/GHC-Base.html#v: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.

@@ -20,7 +20,7 @@ -- PVP summary:     +-+------- breaking API changes --                  | | +----- non-breaking API additions --                  | | | +--- code changes with no API change-version:            0.1.0.0+version:            0.1.0.1  -- A short (one-line) description of the package. synopsis: Lawful list and set monad transformers based on free monads@@ -51,6 +51,7 @@  -- Extra doc files to be distributed with the package, such as a CHANGELOG or a README. extra-doc-files:    CHANGELOG.md+                    README.md  -- Extra source files to be distributed with the package, such as examples, or a tutorial module. -- extra-source-files: