The "free monad transformer" for a functor f

The "free monad" for a functor f.

Wrap a Church-encoding of a "free monad" as the free monad for a functor.

Unwrap the Free monad to obtain it's Church-encoded representation.

Generate a Church-encoded free monad transformer from a FreeT monad transformer.

Convert to a FreeT free monad representation.

Tear down a free monad transformer using iteration.

Tear down a free monad transformer using iteration over a transformer.

Lift a monad homomorphism from m to n into a monad homomorphism from FT f m to FT f n

hoistFT :: (Monad m, Monad n, Functor f) => (m ~> n) -> FT f m ~> FT f n

Lift a natural transformation from f to g into a monad homomorphism from FT f m to FT g n

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.

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:

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

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

http://www.iai.uni-bonn.de/~jv/mpc08.pdf

Convert to another free monad representation.

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

retract is the left inverse of liftF

 retract . liftF = id

Tear down an F Monad using iteration.

Like iter for monadic values.

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.