|Copyright||(C) 2008-2015 Edward Kmett|
|License||BSD-style (see the file LICENSE)|
|Maintainer||Edward Kmett <firstname.lastname@example.org>|
Monads for free
- 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
- 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 :: (Functor m, 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 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))
Monad is one that does no work during the normalization step beyond simply grafting the two monadic values together.
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
data Pair a = Pair a a
And we could make an instance of
MonadFree for it directly:
Moreover, Control.Monad.Free.Church provides a
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
Every "free" functor is left adjoint to some "forgetful" functor.
Free is the left adjoint to
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 functors are
Functor homomorphisms (natural transformations).
Given this isomorphism, every monad homomorphism from
m is equivalent to a natural transformation from
Showing that this isomorphism holds is left as an exercise.
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
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,
A version of lift that can be used with just a Functor for f.
Like iter for monadic values.
Lift a natural transformation from
g into a natural transformation from
The very definition of a free monoid is that given a natural transformation you get a monoid homomorphism.
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 a free monad from a seed.
Unfold a free monad from a seed, monadically.
Prism' (Free f a) a in disguise
preview _Pure (Pure 3)Just 3
review _Pure 3 :: Free Maybe IntPure 3
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))