Copyright (C) 2008-2014 Edward Kmett BSD-style (see the file LICENSE) Edward Kmett provisional non-portable (rank-2 polymorphism, MTPCs) Safe Haskell2010

Description

Synopsis

newtype FT f m a #

The "free monad transformer" for a functor f

Constructors

 FT FieldsrunFT :: forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r

Instances

type F f = FT f Identity #

The "free monad" for a functor f.

free :: (forall r. (a -> r) -> (f r -> r) -> r) -> F f a #

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

runF :: Functor f => F f a -> forall r. (a -> r) -> (f r -> r) -> r #

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

# Operations

improveT :: (Functor f, Monad m) => (forall t. MonadFree f (t m) => t m a) -> FreeT f m a #

Improve the asymptotic performance of code that builds a free monad transformer with only binds and returns by using FT behind the scenes.

Similar to improve.

toFT :: Monad m => FreeT f m a -> FT f m a #

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

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

Convert to a FreeT free monad representation.

iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FT 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) -> FT f m a -> t m a #

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

hoistFT :: (Monad m, Monad n) => (forall a. m a -> n a) -> FT f m b -> FT f n b #

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

transFT :: (forall a. f a -> g a) -> FT f m b -> FT g m b #

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

joinFT :: (Monad m, Traversable f) => FT f m a -> m (F f a) #

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

cutoff :: (Functor f, Monad m) => Integer -> FT f m a -> FT 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.

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

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:

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

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

Convert to another free monad representation.

toF :: Free f a -> F f a #

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

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

retract is the left inverse of liftF

retract . liftF = id


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

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

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

Tear down an F Monad using iteration.

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

Like iter for monadic values.

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