Copyright | (C) 2008-2013 Edward Kmett |
---|---|
License | BSD-style (see the file LICENSE) |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Stability | provisional |
Portability | MPTCs, fundeps |
Safe Haskell | Safe |
Language | Haskell2010 |
Control.Monad.Trans.Free
Description
The free monad transformer
Synopsis
- data FreeF f a b
- newtype FreeT f m a = FreeT { }
- type Free f = FreeT f Identity
- free :: FreeF f a ( Free f a) -> Free f a
- runFree :: Free f a -> FreeF f a ( Free f a)
- liftF :: ( Functor f, MonadFree f m) => f a -> m a
- iterT :: ( Functor f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a
- iterTM :: ( Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a
- hoistFreeT :: ( Functor m, Functor f) => ( forall a. m a -> n a) -> FreeT f m b -> FreeT f n b
- foldFreeT :: ( MonadTrans t, Monad (t m), Monad m) => ( forall n x. Monad n => f x -> t n x) -> FreeT f m a -> t m a
- transFreeT :: ( Monad m, Functor g) => ( forall a. f a -> g a) -> FreeT f m b -> FreeT g m b
- joinFreeT :: ( Monad m, Traversable f) => FreeT f m a -> m ( Free f a)
- cutoff :: ( Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m ( Maybe a)
- partialIterT :: Monad m => Integer -> ( forall a. f a -> m a) -> FreeT f m b -> FreeT f m b
- intersperseT :: ( Monad m, Functor f) => f a -> FreeT f m b -> FreeT f m b
- intercalateT :: ( Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b
- retractT :: ( MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m a
- retract :: Monad f => Free f a -> f a
- iter :: Functor f => (f a -> a) -> Free f a -> a
- iterM :: ( Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a
-
class
Monad
m =>
MonadFree
f m | m -> f
where
- wrap :: f (m a) -> m a
The base functor
The base functor for a free monad.
Instances
The free monad transformer
The "free monad transformer" for a functor
f
Instances
The free monad
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 a Source #
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 Source #
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 Source #
Tear down a free monad transformer using iteration over a transformer.
hoistFreeT :: ( Functor m, Functor f) => ( forall a. m a -> n a) -> FreeT f m b -> FreeT f n b Source #
foldFreeT :: ( MonadTrans t, Monad (t m), Monad m) => ( forall n x. Monad n => f x -> t n x) -> FreeT f m a -> t m a Source #
The very definition of a free monad transformer is that given a natural transformation you get a monad transformer homomorphism.
transFreeT :: ( Monad m, Functor g) => ( forall a. f a -> g a) -> FreeT f m b -> FreeT g m b Source #
joinFreeT :: ( Monad m, Traversable f) => FreeT f m a -> m ( Free f a) Source #
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) 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
is always terminating, provided each of the
steps in the iteration is terminating.
retract
.
cutoff
n
partialIterT :: Monad m => Integer -> ( forall a. f a -> m a) -> FreeT f m b -> FreeT f m b Source #
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 ≡ mpartialIterT
(n+1) phi.
return
≡return
partialIterT
(n+1) phi.
lift
≡lift
partialIterT
(n+1) phi.
wrap
≡join
.lift
. phi
intercalateT :: ( Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b Source #
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 Source #
Tear down a free monad transformer using Monad instance for
t m
.
Operations of free monad
iterM :: ( Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a Source #
Like
iter
for monadic values.
Free Monads With Class
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
smashes the lists flat.
join
[[a]]
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
instanceMonad
Tree wherereturn
= 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:
instanceMonadFree
Pair Tree wherewrap
(Pair l r) = Bin l r
Or we could choose to program with
instead of
Free
Pair
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