| Copyright | (C) 2011-2015 Edward Kmett |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | Edward Kmett <ekmett@gmail.com> |
| Stability | provisional |
| Portability | non-portable (rank-2 polymorphism) |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Control.Monad.Free.Church
Description
"Free Monads for Less"
The most straightforward way of implementing free monads is as a recursive
datatype that allows for arbitrarily deep nesting of the base functor. This is
akin to a tree, with the leaves containing the values, and the nodes being a
level of
Functor
over subtrees.
For each time that the
fmap
or
>>=
operations is used, the old tree is
traversed up to the leaves, a new set of nodes is allocated, and
the old ones are garbage collected. Even if the Haskell runtime
optimizes some of the overhead through laziness and generational garbage
collection, the asymptotic runtime is still quadratic.
On the other hand, if the Church encoding is used, the tree only needs to be constructed once, because:
-
All uses of
fmapare collapsed into a single one, so that the values on the _leaves_ are transformed in one pass.
fmap f . fmap g == fmap (f . g)
-
All uses of
>>=are right associated, so that every new subtree created is final.
(m >>= f) >>= g == m >>= (\x -> f x >>= g)
Asymptotically, the Church encoding supports the monadic operations more
efficiently than the naïve
Free
.
This is based on the "Free Monads for Less" series of articles by Edward Kmett:
Synopsis
-
newtype
F
f a =
F
{
- runF :: forall r. (a -> r) -> (f r -> r) -> r
- improve :: Functor f => ( forall m. MonadFree f m => m a) -> Free f a
- fromF :: MonadFree f m => F f a -> m a
- iter :: (f a -> a) -> F f a -> a
- iterM :: Monad m => (f (m a) -> m a) -> F f a -> m a
- toF :: Functor f => Free f a -> F f a
- retract :: Monad m => F m a -> m a
- hoistF :: ( forall x. f x -> g x) -> F f a -> F g a
- foldF :: Monad m => ( forall x. f x -> m x) -> F f a -> m a
-
class
Monad
m =>
MonadFree
f m | m -> f
where
- wrap :: f (m a) -> m a
- liftF :: ( Functor f, MonadFree f m) => f a -> m a
- cutoff :: Functor f => Integer -> F f a -> F f ( Maybe a)
Documentation
The Church-encoded free monad for a functor
f
.
It is
asymptotically
more efficient to use (
>>=
) for
F
than it is to (
>>=
) with
Free
.
Instances
| MonadTrans F Source # | |
| MonadWriter w m => MonadWriter w ( F m) Source # | |
| MonadState s m => MonadState s ( F m) Source # | |
| MonadReader e m => MonadReader e ( F m) Source # | |
| Functor f => MonadFree f ( F f) Source # | |
| Monad ( F f) Source # | |
| Functor ( F f) Source # | |
| MonadFix ( F f) Source # | |
| Applicative ( F f) Source # | |
| Foldable f => Foldable ( F f) Source # | |
|
Defined in Control.Monad.Free.Church Methods fold :: Monoid m => F f m -> m Source # foldMap :: Monoid m => (a -> m) -> F f a -> m Source # foldMap' :: Monoid m => (a -> m) -> F f a -> m Source # foldr :: (a -> b -> b) -> b -> F f a -> b Source # foldr' :: (a -> b -> b) -> b -> F f a -> b Source # foldl :: (b -> a -> b) -> b -> F f a -> b Source # foldl' :: (b -> a -> b) -> b -> F f a -> b Source # foldr1 :: (a -> a -> a) -> F f a -> a Source # foldl1 :: (a -> a -> a) -> F f a -> a Source # toList :: F f a -> [a] Source # null :: F f a -> Bool Source # length :: F f a -> Int Source # elem :: Eq a => a -> F f a -> Bool Source # maximum :: Ord a => F f a -> a Source # minimum :: Ord a => F f a -> a Source # |
|
| Traversable f => Traversable ( F f) Source # | |
|
Defined in Control.Monad.Free.Church |
|
| Alternative f => Alternative ( F f) Source # |
This violates the Alternative laws, handle with care. |
| MonadPlus f => MonadPlus ( F f) Source # |
This violates the MonadPlus laws, handle with care. |
| MonadCont m => MonadCont ( F m) Source # | |
| Traversable1 f => Traversable1 ( F f) Source # | |
| Apply ( F f) Source # | |
| Bind ( F f) Source # | |
| Foldable1 f => Foldable1 ( F f) Source # | |
improve :: Functor f => ( forall m. MonadFree f m => m a) -> Free f a Source #
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.
toF :: Functor f => Free f a -> F f a Source #
Generate a Church-encoded free monad from a
Free
monad.
hoistF :: ( forall x. f x -> g x) -> F f a -> F g a Source #
Lift a natural transformation from
f
to
g
into a natural transformation from
F f
to
F g
.
foldF :: Monad m => ( forall x. f x -> m x) -> F f a -> m a Source #
The very definition of a free monad is that given a natural transformation you get a monad homomorphism.
class Monad m => MonadFree f m | m -> f where Source #
Monads provide substitution (
fmap
) and renormalization (
join
):
m>>=f =join(fmapf 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
instanceMonadTree 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:
instanceMonadFreePair 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
Instances
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.
cutoff :: Functor f => Integer -> F f a -> F f ( 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