Copyright	(C) 2011-2015 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	provisional
Portability	non-portable (rank-2 polymorphism)
Safe Haskell	Safe
Language	Haskell2010

Control.Monad.Free.Church

Description

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

Synopsis

Documentation

newtype F f a Source

The Church-encoded free monad for a functor f.

It is asymptotically more efficient to use (>>=) for F than it is to (>>=) with Free.

http://comonad.com/reader/2011/free-monads-for-less-2/

Constructors

F
Fields runF :: forall r. (a -> r) -> (f r -> r) -> r

Instances

MonadTrans F Source
MonadReader e m => MonadReader e (F m) Source
MonadState s m => MonadState s (F m) Source
MonadWriter w m => MonadWriter w (F m) Source
Functor f => MonadFree f (F f) Source
Monad (F f) Source
Functor (F f) Source
MonadFix (F f) Source
Applicative (F f) Source
(Foldable f, Functor f) => Foldable (F f) Source
Alternative f => Alternative (F f) Source	This violates the Alternative laws, handle with care.
MonadPlus f => MonadPlus (F f) Source	This violates the MonadPlus laws, handle with care.
MonadCont m => MonadCont (F m) Source
Apply (F f) Source
Bind (F f) Source

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

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.

fromF :: MonadFree f m => F f a -> m a Source

Convert to another free monad representation.

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

Like iter for monadic values.

toF :: Functor f => Free f a -> F f a Source

Generate a Church-encoded free monad from a Free monad.

retract :: Monad m => F m a -> m a Source

retract is the left inverse of lift and liftF

retract . lift = id
retract . liftF = id

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

Lift a natural transformation from f to g into a natural transformation from F f to F g.

foldF :: Monad m => (forall x. f x -> m x) -> F f a -> m a Source

The very definition of a free monoid is that given a natural transformation you get a monoid homomorphism.

class Monad m => MonadFree f m | m -> f where Source

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 join [[a]] smashes the lists flat.

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 Free Pair instead of 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.

Minimal complete definition

Nothing

Methods

wrap :: f (m a) -> m a Source

Add a layer.

wrap (fmap f x) ≡ wrap (fmap return x) >>= f

Instances

(Functor f, MonadFree f m) => MonadFree f (ListT m) Source
(Functor f, MonadFree f m) => MonadFree f (IdentityT m) Source
(Functor f, MonadFree f m) => MonadFree f (MaybeT m) Source
Functor f => MonadFree f (Free f) Source
Functor f => MonadFree f (F f) Source
Monad m => MonadFree Identity (IterT m) Source
(Functor f, MonadFree f m, Error e) => MonadFree f (ErrorT e m) Source
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) Source
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) Source
(Functor f, MonadFree f m) => MonadFree f (ContT r m) Source
(Functor f, MonadFree f m) => MonadFree f (StateT s m) Source
(Functor f, MonadFree f m) => MonadFree f (StateT s m) Source
(Functor f, MonadFree f m) => MonadFree f (ReaderT e m) Source
(Functor f, Monad m) => MonadFree f (FreeT f m) Source
MonadFree f (FT f m) Source
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) Source
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) Source

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

A version of lift that can be used with just a Functor for f.

cutoff :: Functor f => Integer -> F f a -> F f (Maybe a) Source

Cuts off a tree of computations at a given depth. If the depth is 0 or less, no computation nor monadic effects will take place.

Some examples (n ≥ 0):

cutoff 0     _        == return Nothing

cutoff (n+1) . return == return . Just

cutoff (n+1) . lift   == lift . liftM Just

cutoff (n+1) . wrap   == wrap . fmap (cutoff n)

Calling retract . cutoff n is always terminating, provided each of the steps in the iteration is terminating.