|Maintainer||Edward Kmett <firstname.lastname@example.org>|
Monads for free
- class Monad m => MonadFree f m | m -> f where
- wrap :: f (m a) -> m a
- data Free f a
- retract :: Monad f => Free f a -> f a
- liftF :: Functor f => f a -> Free f a
- iter :: Functor f => (f a -> a) -> Free f a -> a
- hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
Monad is one that does no work during the normalization step beyond simply grafting the two monadic values together.
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
data Pair a = Pair a a
And we could make an instance of
MonadFree for it directly:
Every "free" functor is left adjoint to some "forgetful" functor.
Free is the left adjoint to
Free being left adjoint to
U means that there is an isomorphism between
in the category of monads and
Free f -> m
f -> U m in the category of functors.
Morphisms in the category of functors are
Functor homomorphisms (natural transformations).
Given this isomorphism, every monad homomorphism from
m is equivalent to a natural transformation from
Showing that this isomorphism holds is left as an exercise.
This can be very useful for modeling domain specific languages, trees, or other constructs.
This instance of
MonadFree is fairly naive about the encoding. For more efficient free monad implementations that require additional
extensions and thus aren't included here, you may want to look at the
A number of common monads arise as free monads,