Portability | MPTCs, fundeps |
---|---|

Stability | provisional |

Maintainer | Edward Kmett <ekmett@gmail.com> |

Safe Haskell | None |

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

instance`Monad`

Tree where`return`

= 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:

instance`MonadFree`

Pair Tree where`wrap`

(Pair l r) = Bin l r

Or we could choose to program with

instead of `Free`

Pair`Tree`

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`

.

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`

.

Being `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 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

to `Free`

f`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

as many layers of `Free`

f a`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 implementations that require additional
extensions and thus aren't included here, you may want to look at the `kan-extensions`

package.

A number of common monads arise as free monads,