Copyright (C) 2008-2013 Edward Kmett BSD-style (see the file LICENSE) Edward Kmett provisional MPTCs, fundeps Safe Haskell2010

Description

The free monad transformer

Synopsis

# The base functor

data FreeF f a b #

The base functor for a free monad.

Constructors

 Pure a Free (f b)

Instances

# The free monad

type Free f = FreeT f Identity #

The "free monad" for a functor f.

free :: FreeF f a (Free f a) -> Free f a #

Pushes a layer into a free monad value.

runFree :: Free f a -> FreeF f a (Free f a) #

Evaluates the first layer out of a free monad value.

# Operations

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

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

iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a #

Tear down a free monad transformer using iteration.

iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a #

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

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

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

hoistFreeT :: (Monad m, Functor f) => (m ~> n) -> FreeT f m ~> FreeT f n

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

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

joinFreeT :: (Monad m, Traversable f) => FreeT f m a -> m (Free f a) #

Pull out and join m layers of FreeT f m a.

cutoff :: (Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a) #

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.

partialIterT :: Monad m => Integer -> (forall a. f a -> m a) -> FreeT f m b -> FreeT f m b #

partialIterT n phi m interprets first n layers of m using phi. This is sort of the opposite for cutoff.

Some examples (n ≥ 0):

partialIterT 0 _ m              ≡ m
partialIterT (n+1) phi . return ≡ return
partialIterT (n+1) phi . lift   ≡ lift
partialIterT (n+1) phi . wrap   ≡ join . lift . phi


intersperseT :: (Monad m, Functor f) => f a -> FreeT f m b -> FreeT f m b #

intersperseT f m inserts a layer f between every two layers in m.

intersperseT f . return ≡ return
intersperseT f . lift   ≡ lift
intersperseT f . wrap   ≡ wrap . fmap (iterTM (wrap . (<\$ f) . wrap))


intercalateT :: (Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b #

intercalateT f m inserts a layer f between every two layers in m and then retracts the result.

intercalateT f ≡ retractT . intersperseT f


retractT :: (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m a #

Tear down a free monad transformer using Monad instance for t m.

# Operations of free monad

retract :: Monad f => Free f a -> f a #

retract is the left inverse of liftF

retract . liftF = id


iter :: Functor f => (f a -> a) -> Free f a -> a #

Tear down a Free Monad using iteration.

iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a #

Like iter for monadic values.

# Free Monads With Class

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

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.

Methods

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

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


wrap :: (m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a #

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