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

Stability | provisional |

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

Safe Haskell | None |

The free monad transformer

- data FreeF f a b
- newtype FreeT f m a = FreeT {}
- class Monad m => MonadFree f m | m -> f where
- wrap :: f (m a) -> m a

- liftF :: (Functor f, Monad m) => f a -> FreeT f m a
- hoistFreeT :: (Monad m, Functor f) => (forall a. m a -> n a) -> FreeT f m b -> FreeT f n b
- transFreeT :: (Monad m, Functor g) => (forall a. f a -> g a) -> FreeT f m b -> FreeT g m b

# Documentation

The base functor for a free monad.

Typeable1 f => Typeable2 (FreeF f) | |

(Bifunctor (FreeF f), Bifoldable (FreeF f), Traversable f) => Bitraversable (FreeF f) | |

Functor f => Bifunctor (FreeF f) | |

Foldable f => Bifoldable (FreeF f) | |

Functor f => Functor (FreeF f a) | |

Foldable f => Foldable (FreeF f a) | |

(Functor (FreeF f a), Foldable (FreeF f a), Traversable f) => Traversable (FreeF f a) | |

(Eq a, Eq (f b)) => Eq (FreeF f a b) | |

(Typeable (FreeF f a b), Typeable1 f, Typeable a, Typeable b, Data a, Data (f b), Data b) => Data (FreeF f a b) | |

(Eq (FreeF f a b), Ord a, Ord (f b)) => Ord (FreeF f a b) | |

(Read a, Read (f b)) => Read (FreeF f a b) | |

(Show a, Show (f b)) => Show (FreeF f a b) |

The "free monad transformer" for a functor `f`

.

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`

.

liftF :: (Functor f, Monad m) => f a -> FreeT f m aSource

FreeT is a functor from the category of functors to the category of monads.

This provides the mapping.