The
Free Monad for a
Functor f.
Formally
A
Monad n is a free
Monad for
f if
every monad homomorphism from
n to another monad
m
is equivalent to a natural transformation from
f to
m.
Why Free?
Every "free" functor is left adjoint to some "forgetful" functor.
If we define a forgetful functor
U from the category of
monads to the category of functors that just forgets the
Monad,
leaving only the
Functor. i.e.
U (M,return,join) = M
then
Free is the left adjoint to
U.
Free being left adjoint to
U means that there is an
isomorphism between
Free f -> m in the category of monads and
f
-> U m in the category of functors.
Morphisms in the category of monads are
Monad homomorphisms
(natural transformations that respect
return and
join).
Morphisms in the category of functors are
Functor homomorphisms
(natural transformations).
Given this isomorphism, every monad homomorphism from
Free
f to
m is equivalent to a natural transformation from
f to
m
Showing that this isomorphism holds is left as an exercise.
In practice, you can just view a
Free f a as many
layers of
f wrapped around values of type
a, where
(>>=) performs substitution and grafts new
layers of
f in for each of the free variables.
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 implementation see
Control.Monad.Free.Church, in particular note the
improve combinator. You may also want to take a look at the
kan-extensions package
(
http://hackage.haskell.org/package/kan-extensions).
A number of common monads arise as free monads,
- Given data Empty a, Free Empty is
isomorphic to the Identity monad.
- Free Maybe can be used to model a
partiality monad where each layer represents running the computation
for a while longer.