Portability | non-portable (rank-2 polymorphism) |
---|---|

Stability | provisional |

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

Safe Haskell | None |

"Free Monads for Less"

The most straightforward way of implementing free monads is as a recursive
datatype that allows for arbitrarily deep nesting of the base functor. This is
akin to a tree, with the leaves containing the values, and the nodes being a
level of `Functor`

over subtrees.

For each time that the `fmap`

or `>>=`

operations is used, the old tree is
traversed up to the leaves, a new set of nodes is allocated, and
the old ones are garbage collected. Even if the Haskell runtime
optimizes some of the overhead through laziness and generational garbage
collection, the asymptotic runtime is still quadratic.

On the other hand, if the Church encoding is used, the tree only needs to be constructed once, because:

- All uses of
`fmap`

are collapsed into a single one, so that the values on the _leaves_ are transformed in one pass.

fmap f . fmap g == fmap (f . g)

- All uses of
`>>=`

are right associated, so that every new subtree created is final.

(m >>= f) >>= g == m >>= (\x -> f x >>= g)

Asymptotically, the Church encoding supports the monadic operations more
efficiently than the naïve `Free`

.

This is based on the "Free Monads for Less" series of articles by Edward Kmett:

- newtype F f a = F {
- runF :: forall r. (a -> r) -> (f r -> r) -> r

- improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
- fromF :: MonadFree f m => F f a -> m a
- iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> F f a -> m a
- toF :: Functor f => Free f a -> F f a
- retract :: Monad m => F m a -> m a
- hoistF :: (forall x. f x -> g x) -> F f a -> F g a
- class Monad m => MonadFree f m | m -> f where
- wrap :: f (m a) -> m a

- liftF :: (Functor f, MonadFree f m) => f a -> m a

# Documentation

The Church-encoded free monad for a functor `f`

.

It is *asymptotically* more efficient to use (`>>=`

) for `F`

than it is to (`>>=`

) with `Free`

.

MonadTrans F | |

MonadReader e m => MonadReader e (F m) | |

MonadState s m => MonadState s (F m) | |

MonadWriter w m => MonadWriter w (F m) | |

Functor f => MonadFree f (F f) | |

Monad (F f) | |

Functor (F f) | |

MonadFix (F f) | |

MonadPlus f => MonadPlus (F f) | |

Applicative (F f) | |

Alternative f => Alternative (F f) | |

MonadCont m => MonadCont (F m) | |

Apply (F f) | |

Bind (F f) |

improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f aSource

Improve the asymptotic performance of code that builds a free monad with only binds and returns by using `F`

behind the scenes.

This is based on the "Free Monads for Less" series of articles by Edward Kmett:

and \"Asymptotic Improvement of Computations over Free Monads\" by Janis Voightländer.

iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> F f a -> m aSource

Like iter for monadic values.

hoistF :: (forall x. f x -> g x) -> F f a -> F g aSource

Lift a natural transformation from `f`

to `g`

into a natural transformation from `F f`

to `F g`

.

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, Control.Monad.Free.Church provides a `MonadFree`

instance that can improve the *asymptotic* complexity of code that
constructs free monads by effectively reassociating the use of
(`>>=`

). You may also want to take a look at the `kan-extensions`

package (http://hackage.haskell.org/package/kan-extensions).

See `Free`

for a more formal definition of the free `Monad`

for a `Functor`

.

(Functor f, MonadFree f m) => MonadFree f (ListT m) | |

(Functor f, MonadFree f m) => MonadFree f (IdentityT m) | |

(Functor f, MonadFree f m) => MonadFree f (MaybeT m) | |

Functor f => MonadFree f (Free f) | |

Functor f => MonadFree f (F f) | |

Monad m => MonadFree Identity (IterT m) | |

(Functor f, MonadFree f m, Error e) => MonadFree f (ErrorT e m) | |

(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) | |

(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) | |

(Functor f, MonadFree f m) => MonadFree f (ContT r m) | |

(Functor f, MonadFree f m) => MonadFree f (StateT s m) | |

(Functor f, MonadFree f m) => MonadFree f (StateT s m) | |

(Functor f, MonadFree f m) => MonadFree f (ReaderT e m) | |

(Functor f, Monad m) => MonadFree f (FreeT f m) | |

Functor f => MonadFree f (FT f m) | |

(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) | |

(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) |