| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Control.Monad.Free.Ap
Description
"Applicative Effects in Free Monads"
Often times, the
(\<*\>)
operator can be more efficient than
ap
.
Conventional free monads don't provide any means of modeling this.
The free monad can be modified to make use of an underlying applicative.
But it does require some laws, or else the
(\<*\>)
=
ap
law is broken.
When interpreting this free monad with
foldFree
,
the natural transformation must be an applicative homomorphism.
An applicative homomorphism
hm :: (Applicative f, Applicative g) => f x -> g x
will satisfy these laws.
-
hm (pure a) = pure a
-
hm (f <*> a) = hm f <*> hm a
This is based on the "Applicative Effects in Free Monads" series of articles by Will Fancher
Synopsis
-
class
Monad
m =>
MonadFree
f m | m -> f
where
- wrap :: f (m a) -> m a
- data Free f a
- retract :: ( Applicative f, Monad f) => Free f a -> f a
- liftF :: ( Functor f, MonadFree f m) => f a -> m a
- iter :: Applicative f => (f a -> a) -> Free f a -> a
- iterA :: ( Applicative p, Applicative f) => (f (p a) -> p a) -> Free f a -> p a
- iterM :: ( Applicative m, Monad m, Applicative f) => (f (m a) -> m a) -> Free f a -> m a
- hoistFree :: ( Applicative f, Applicative g) => ( forall a. f a -> g a) -> Free f b -> Free g b
- foldFree :: ( Applicative f, Applicative m, Monad m) => ( forall x. f x -> m x) -> Free f a -> m a
- toFreeT :: ( Applicative f, Applicative m, Monad m) => Free f a -> FreeT f m a
- cutoff :: Applicative f => Integer -> Free f a -> Free f ( Maybe a)
- unfold :: Applicative f => (b -> Either a (f b)) -> b -> Free f a
- unfoldM :: ( Applicative f, Traversable f, Applicative m, Monad m) => (b -> m ( Either a (f b))) -> b -> m ( Free f a)
- _Pure :: forall f m a p. ( Choice p, Applicative m) => p a (m a) -> p ( Free f a) (m ( Free f a))
- _Free :: forall f m a p. ( Choice p, Applicative m) => p (f ( Free f a)) (m (f ( Free f a))) -> p ( Free f a) (m ( Free f a))
Documentation
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
A free monad given an applicative
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.
iter :: Applicative f => (f a -> a) -> Free f a -> a Source #
iterA :: ( Applicative p, Applicative f) => (f (p a) -> p a) -> Free f a -> p a Source #
Like
iter
for applicative values.
iterM :: ( Applicative m, Monad m, Applicative f) => (f (m a) -> m a) -> Free f a -> m a Source #
Like
iter
for monadic values.
hoistFree :: ( Applicative f, Applicative g) => ( forall a. f a -> g a) -> Free f b -> Free g b Source #
foldFree :: ( Applicative f, Applicative m, Monad m) => ( forall x. f x -> m x) -> Free f a -> m a Source #
Given an applicative homomorphism, you get a monad homomorphism.
toFreeT :: ( Applicative f, Applicative m, Monad m) => Free f a -> FreeT f m a Source #
Convert a
Free
monad from
Control.Monad.Free.Ap
to a
FreeT
monad
from
Control.Monad.Trans.Free.Ap
.
WARNING: This assumes that
liftF
is an applicative homomorphism.
cutoff :: Applicative f => Integer -> Free f a -> Free 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 'retract . cutoff n' is always terminating, provided each of the steps in the iteration is terminating.
unfold :: Applicative f => (b -> Either a (f b)) -> b -> Free f a Source #
Unfold a free monad from a seed.
unfoldM :: ( Applicative f, Traversable f, Applicative m, Monad m) => (b -> m ( Either a (f b))) -> b -> m ( Free f a) Source #
Unfold a free monad from a seed, monadically.
_Pure :: forall f m a p. ( Choice p, Applicative m) => p a (m a) -> p ( Free f a) (m ( Free f a)) Source #
This is
Prism' (Free f a) a
in disguise
>>>preview _Pure (Pure 3)Just 3
>>>review _Pure 3 :: Free Maybe IntPure 3
_Free :: forall f m a p. ( Choice p, Applicative m) => p (f ( Free f a)) (m (f ( Free f a))) -> p ( Free f a) (m ( Free f a)) Source #
This is
Prism' (Free f a) (f (Free f a))
in disguise
>>>preview _Free (review _Free (Just (Pure 3)))Just (Just (Pure 3))
>>>review _Free (Just (Pure 3))Free (Just (Pure 3))