Copyright | (C) 2008-2015 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 |

Monads for free

## Synopsis

- class Monad m => MonadFree f m | m -> f where
- wrap :: f (m a) -> m a

- data Free f a
- retract :: Monad f => Free f a -> f a
- liftF :: (Functor f, MonadFree f m) => f a -> m a
- iter :: Functor f => (f a -> a) -> Free f a -> a
- iterA :: (Applicative p, Functor f) => (f (p a) -> p a) -> Free f a -> p a
- iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a
- hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
- foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a
- toFreeT :: (Functor f, Monad m) => Free f a -> FreeT f m a
- cutoff :: Functor f => Integer -> Free f a -> Free f (Maybe a)
- unfold :: Functor f => (b -> Either a (f b)) -> b -> Free f a
- unfoldM :: (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 g m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (g (Free g a))) -> p (Free f a) (m (Free g a))

# Documentation

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

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`

.

Nothing

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 #

Add a layer.

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

## Instances

The `Free`

`Monad`

for a `Functor`

`f`

.

*Formally*

A `Monad`

`n`

is a free `Monad`

for `f`

if every monad homomorphism
from `n`

to another monad `m`

is equivalent to a natural transformation
from `f`

to `m`

.

*Why Free?*

Every "free" functor is left adjoint to some "forgetful" functor.

If we define a forgetful functor `U`

from the category of monads to the category of functors
that just forgets the `Monad`

, leaving only the `Functor`

. i.e.

U (M,`return`

,`join`

) = M

then `Free`

is the left adjoint to `U`

.

Being `Free`

being left adjoint to `U`

means that there is an isomorphism between

in the category of monads and `Free`

f -> m`f -> U m`

in the category of functors.

Morphisms in the category of monads are `Monad`

homomorphisms (natural transformations that respect `return`

and `join`

).

Morphisms in the category of functors are `Functor`

homomorphisms (natural transformations).

Given this isomorphism, every monad homomorphism from

to `Free`

f`m`

is equivalent to a natural transformation from `f`

to `m`

Showing that this isomorphism holds is left as an exercise.

In practice, you can just view a

as many layers of `Free`

f a`f`

wrapped around values of type `a`

, where
`(`

performs substitution and grafts new layers of `>>=`

)`f`

in for each of the free variables.

This can be very useful for modeling domain specific languages, trees, or other constructs.

This instance of `MonadFree`

is fairly naive about the encoding. For more efficient free monad implementation see Control.Monad.Free.Church, in particular note the `improve`

combinator.
You may also want to take a look at the `kan-extensions`

package (http://hackage.haskell.org/package/kan-extensions).

A number of common monads arise as free monads,

## Instances

MonadTrans Free # | This is not a true monad transformer. It is only a monad transformer "up to |

Defined in Control.Monad.Free | |

(Functor m, MonadWriter e m) => MonadWriter e (Free m) # | |

(Functor m, MonadState s m) => MonadState s (Free m) # | |

(Functor m, MonadReader e m) => MonadReader e (Free m) # | |

(Functor m, MonadError e m) => MonadError e (Free m) # | |

Defined in Control.Monad.Free throwError :: e -> Free m a # catchError :: Free m a -> (e -> Free m a) -> Free m a # | |

Functor f => MonadFree f (Free f) # | |

Defined in Control.Monad.Free | |

Functor f => Monad (Free f) # | |

Functor f => Functor (Free f) # | |

Functor f => MonadFix (Free f) # | |

Defined in Control.Monad.Free | |

Functor f => Applicative (Free f) # | |

Foldable f => Foldable (Free f) # | |

Defined in Control.Monad.Free fold :: Monoid m => Free f m -> m # foldMap :: Monoid m => (a -> m) -> Free f a -> m # foldr :: (a -> b -> b) -> b -> Free f a -> b # foldr' :: (a -> b -> b) -> b -> Free f a -> b # foldl :: (b -> a -> b) -> b -> Free f a -> b # foldl' :: (b -> a -> b) -> b -> Free f a -> b # foldr1 :: (a -> a -> a) -> Free f a -> a # foldl1 :: (a -> a -> a) -> Free f a -> a # elem :: Eq a => a -> Free f a -> Bool # maximum :: Ord a => Free f a -> a # minimum :: Ord a => Free f a -> a # | |

Traversable f => Traversable (Free f) # | |

Eq1 f => Eq1 (Free f) # | |

Ord1 f => Ord1 (Free f) # | |

Defined in Control.Monad.Free | |

Read1 f => Read1 (Free f) # | |

Defined in Control.Monad.Free | |

Show1 f => Show1 (Free f) # | |

Alternative v => Alternative (Free v) # | This violates the Alternative laws, handle with care. |

(Functor v, MonadPlus v) => MonadPlus (Free v) # | This violates the MonadPlus laws, handle with care. |

(Functor m, MonadCont m) => MonadCont (Free m) # | |

Traversable1 f => Traversable1 (Free f) # | |

Foldable1 f => Foldable1 (Free f) # | |

Functor f => Apply (Free f) # | |

Functor f => Bind (Free f) # | |

Functor f => Generic1 (Free f :: Type -> Type) # | |

(Eq1 f, Eq a) => Eq (Free f a) # | |

(Typeable f, Data (f (Free f a)), Data a) => Data (Free f a) # | |

Defined in Control.Monad.Free gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Free f a -> c (Free f a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Free f a) # toConstr :: Free f a -> Constr # dataTypeOf :: Free f a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Free f a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Free f a)) # gmapT :: (forall b. Data b => b -> b) -> Free f a -> Free f a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Free f a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Free f a -> r # gmapQ :: (forall d. Data d => d -> u) -> Free f a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Free f a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Free f a -> m (Free f a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Free f a -> m (Free f a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Free f a -> m (Free f a) # | |

(Ord1 f, Ord a) => Ord (Free f a) # | |

Defined in Control.Monad.Free | |

(Read1 f, Read a) => Read (Free f a) # | |

(Show1 f, Show a) => Show (Free f a) # | |

Generic (Free f a) # | |

type Rep1 (Free f :: Type -> Type) # | |

Defined in Control.Monad.Free type Rep1 (Free f :: Type -> Type) = D1 (MetaData "Free" "Control.Monad.Free" "free-5.1-4UATSEhaXgTAvcVwsU7IL6" False) (C1 (MetaCons "Pure" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1) :+: C1 (MetaCons "Free" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (f :.: Rec1 (Free f)))) | |

type Rep (Free f a) # | |

Defined in Control.Monad.Free type Rep (Free f a) = D1 (MetaData "Free" "Control.Monad.Free" "free-5.1-4UATSEhaXgTAvcVwsU7IL6" False) (C1 (MetaCons "Pure" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)) :+: C1 (MetaCons "Free" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (f (Free f a))))) |

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

A version of lift that can be used with just a Functor for f.

iterA :: (Applicative p, Functor f) => (f (p a) -> p a) -> Free f a -> p a #

Like `iter`

for applicative values.

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b #

Lift a natural transformation from `f`

to `g`

into a natural transformation from

to `FreeT`

f

.`FreeT`

g

foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a #

The very definition of a free monad is that given a natural transformation you get a monad homomorphism.

toFreeT :: (Functor f, Monad m) => Free f a -> FreeT f m a #

Convert a `Free`

monad from Control.Monad.Free to a `FreeT`

monad
from Control.Monad.Trans.Free.

cutoff :: Functor f => Integer -> Free f a -> Free f (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.

unfoldM :: (Traversable f, Applicative m, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f a) #

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

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 g m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (g (Free g a))) -> p (Free f a) (m (Free g a)) #

This is `Prism (Free f a) (Free g a) (f (Free f a)) (g (Free g a))`

in disguise

`>>>`

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

`>>>`

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