Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

"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
- 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`

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

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

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`

.

wrap :: f (m a) -> m a Source #

Add a layer.

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 Source #

Add a layer.

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

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

`>>>`

Just 3`preview _Pure (Pure 3)`

`>>>`

Pure 3`review _Pure 3 :: Free Maybe Int`

_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

`>>>`

Just (Just (Pure 3))`preview _Free (review _Free (Just (Pure 3)))`

`>>>`

Free (Just (Pure 3))`review _Free (Just (Pure 3))`