Portability	MPTCs, fundeps
Stability	provisional
Maintainer	Edward Kmett <ekmett@gmail.com>
Safe Haskell	None

Control.Monad.Trans.Free

Contents

The base functor
The free monad transformer
The free monad
Operations
Operations of free monad
Free Monads With Class

Description

The free monad transformer

Synopsis

The base functor

data FreeF f a b Source

The base functor for a free monad.

Constructors

Pure a
Free (f b)

Instances

Typeable1 f => Typeable2 (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)
Traversable f => Traversable (FreeF f a)
(Eq a, Eq (f b)) => Eq (FreeF f a b)
(Typeable1 f, Typeable a, Typeable b, Data a, Data (f b), Data b) => Data (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

newtype FreeT f m a Source

The "free monad transformer" for a functor f

Constructors

FreeT
Fields runFreeT :: m (FreeF f a (FreeT f m a))

Instances

(Functor f, MonadError e m) => MonadError e (FreeT f m)
(Functor f, MonadReader r m) => MonadReader r (FreeT f m)
(Functor f, MonadState s m) => MonadState s (FreeT f m)
(Functor f, MonadWriter w m) => MonadWriter w (FreeT f m)
(Functor f, Monad m) => MonadFree f (FreeT f m)
MonadTrans (FreeT f)
(Functor f, Monad m) => Monad (FreeT f m)
(Functor f, Monad m) => Functor (FreeT f m)
(Typeable1 f, Typeable1 w) => Typeable1 (FreeT f w)
(Functor f, MonadPlus m) => MonadPlus (FreeT f m)
(Functor f, Monad m) => Applicative (FreeT f m)
(Foldable m, Foldable f) => Foldable (FreeT f m)
(Monad m, Traversable m, Traversable f) => Traversable (FreeT f m)
(Functor f, MonadPlus m) => Alternative (FreeT f m)
(Functor f, MonadIO m) => MonadIO (FreeT f m)
(Functor f, MonadCont m) => MonadCont (FreeT f m)
(Functor f, Monad m) => Apply (FreeT f m)
(Functor f, Monad m) => Bind (FreeT f m)
Eq (m (FreeF f a (FreeT f m a))) => Eq (FreeT f m a)
(Typeable1 f, Typeable1 w, Typeable a, Data (w (FreeF f a (FreeT f w a))), Data a) => Data (FreeT f w a)
Ord (m (FreeF f a (FreeT f m a))) => Ord (FreeT f m a)
Read (m (FreeF f a (FreeT f m a))) => Read (FreeT f m a)
Show (m (FreeF f a (FreeT f m a))) => Show (FreeT f m a)

The free monad

type Free f = FreeT f Identity Source

The "free monad" for a functor f.

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

Pushes a layer into a free monad value.

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

Evaluates the first layer out of a free monad value.

Operations

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

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 aSource

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 aSource

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 bSource

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 bSource

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

Operations of free monad

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

retract is the left inverse of liftF

 retract . liftF = id

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

Tear down a Free Monad using iteration.

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

Like iter for monadic values.

Free Monads With Class

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 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 aSource

Add a layer.

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

Instances

(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)