Portability MPTCs, fundeps provisional Edward Kmett None

Description

Synopsis

# Documentation

class Monad m => MonadFree f m | m -> f whereSource

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 join [[a]] smashes the lists flat.

On the other hand, consider:

data Tree a = Bin (Tree a) (Tree a) | Tip a
return = Tip
Tip a >>= f = f a
Bin l r >>= f = Bin (l >>= f) (r >>= f)

data Pair a = Pair a a

And we could make an instance of MonadFree for it directly:

wrap (Pair l r) = Bin l r

Or we could choose to program with Free Pair instead of Tree and thereby avoid having to define our own Monad instance.

Moreover, the kan-extensions package provides MonadFree instances that can improve the asymptotic complexity of code that constructors free monads by effectively reassociating the use of (>>=).

See Free for a more formal definition of the free Monad for a Functor.

Methods

wrap :: f (m a) -> m aSource

Instances

data Free f a Source

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

Free f -> m in the category of monads and 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 Free f to 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 Free f a as many layers of 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 implementations that require additional extensions and thus aren't included here, you may want to look at the kan-extensions package.

• Given data Empty a, Free Empty is isomorphic to the Identity monad.
• Free Maybe can be used to model a partiality monad where each layer represents running the computation for a while longer.

Constructors

 Pure a Free (f (Free f a))

Instances

retract :: Monad f => Free f a -> f aSource

retract is the left inverse of lift and liftF

retract . lift = id
retract . liftF = id

liftF :: Functor f => f a -> Free f aSource

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

iter :: Functor f => (f a -> a) -> Free f a -> aSource

Tear down a Free Monad using iteration.

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

Lift a natural transformation from f to g into a natural transformation from FreeT f to FreeT g.