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
- 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 :: 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 :: (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, Monad m) => (forall x. f x -> m x) -> Free f a -> m a
- toFreeT :: (Applicative f, 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, 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`

.

Nothing

#### Instances

A free monad given an applicative

#### Instances

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

Defined in Control.Monad.Free.Ap | |

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

Applicative f => MonadFree f (Free f) Source # | |

MonadError e m => MonadError e (Free m) Source # | |

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

MonadReader e m => MonadReader e (Free m) Source # | |

MonadState s m => MonadState s (Free m) Source # | |

MonadWriter e m => MonadWriter e (Free m) Source # | |

Applicative f => MonadFix (Free f) Source # | |

Defined in Control.Monad.Free.Ap | |

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

Defined in Control.Monad.Free.Ap fold :: Monoid m => Free f m -> m # foldMap :: Monoid m => (a -> m) -> Free f a -> 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 # | |

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

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

Defined in Control.Monad.Free.Ap | |

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

Defined in Control.Monad.Free.Ap | |

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

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

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

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

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

Applicative f => Monad (Free f) Source # | |

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

MonadCont m => MonadCont (Free m) Source # | |

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

Apply f => Bind (Free f) Source # | |

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

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

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

Defined in Control.Monad.Free.Ap 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 :: forall r r'. (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) # | |

Generic (Free f a) Source # | |

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

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

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

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

Defined in Control.Monad.Free.Ap | |

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

Defined in Control.Monad.Free.Ap type Rep1 (Free f :: Type -> Type) = D1 ('MetaData "Free" "Control.Monad.Free.Ap" "free-5.2-8yEobwXBbzsEnejCWouYBv" '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) Source # | |

Defined in Control.Monad.Free.Ap type Rep (Free f a) = D1 ('MetaData "Free" "Control.Monad.Free.Ap" "free-5.2-8yEobwXBbzsEnejCWouYBv" '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 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 :: (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, 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, 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, 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))`