Portability | non-portable (fundeps, MPTCs) |
---|---|
Stability | experimental |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Safe Haskell | Safe-Inferred |
Monads for free.
Documentation
class Monad m => MonadFree f m | m -> f whereSource
Monads provide substitution (fmap
) and renormalization (join
):
m>>=
f =join
.fmap
f m
A free Monad
is one that does no work during the normalization step beyond simply grafting the two monadic values together.
[]
is not a free Monad
(in this sense) because
smashes the lists flat.
join
[[a]]
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
instanceMonad
Tree wherereturn
= Tip Tip a>>=
f = f a Bin l r>>=
f = Bin (l>>=
f) (r>>=
f)
This Monad
is the free Monad
of Pair:
data Pair a = Pair a a
And we could make an instance of MonadFree
for it directly:
instanceMonadFree
Pair Tree wherewrap
(Pair l r) = Bin l r
Or we could choose to program with
instead of Free
PairTree
and thereby avoid having to define our own Monad
instance.
Moreover, the kan-extensions
package provides MonadFree
instances that can
improve the asymptotic complexity of code that constructors free monads by
effectively reassociating the use of (>>=
).
See Free
for a more formal definition of the free Monad
for a Functor
.