1 Functors and Free Monads

{-# LANGUAGE RankNTypes #-}

data F f = F {
    _map :: forall a b. (a -> b) -> f a -> f b
}

An instance of F should contain a function called _map constrained by whichever base type is being functor-ized.

data Mu f a
    = Term { retract :: a }
    | Cont (f (Mu f a))

Mu is the free monad. I like calling it Mu for two reasons: because calling it “free” is confusing and not informative; and because Mu behaves like the type-level analog to the Y-combinator, called Mu.

unit :: a -> Mu f a
unit = Term

yield :: a -> Mu f a
yield = Term

These two are different names for the same thing, mostly for aesthetic reasons. You’ll see.

bind :: F f -> Mu f a -> (a -> Mu f b) -> Mu f b
bind i arg fn = case arg of
   Term t      -> fn t
   Cont k      -> Cont (map (bind' fn) k)

   where map   = _map i
         bind' = flip (bind i)

This is the cool part. bind is defined for any type which is wrapped by Mu, and for a type to be wrapped by Mu it must instantiate our F type. Thus we can ask for an “instance” argument, called i here.

sequence' i x   = case x of
    []      -> unit []
    m:ms    -> m              >>= \x  ->
               sequence' i ms >>= \xs ->
               unit (x:xs)
    where
        (>>=) = bind i

2 An example: re-creating the Maybe monad.

Think of how much time we have collectively lost to massive failure due to null pointer errors. Now behold how simple optional types are to implement, and weep:

data Optional s
    = Nil
    | Some s
    deriving (Show)

Now for the fun part. I will create an F instance for Optional along with some convenience functions to use in monadic computations. While I don’t do it here, this could be derived automatically.

fOptional :: F Optional
fOptional = F {
    _map = \f x -> case x of
        Nil     -> Nil
        Some s  -> Some $ f s
}

nil = Cont Nil
some = Term

In ~12 lines of real code, I have created a Maybe clone and proven it is a functor. As a result all the remaining code necessary to compose a monad has been derived automatically.

Since this was a free monad, the only remaining code is that to “run” the monadic computation built up using unit and bind.

runOptional :: Mu Optional a -> Optional a
runOptional (Term t) = Some t
runOptional (Cont k) = case k of
    Nil     -> Nil
    Some v  -> runOptional v

3 Tests!

Without further ado, here is some example code written in our Optional monad.

testOptional1 = some 5 >>= \a ->
                some 6 >>= \b ->
                yield $ a * b
    where (>>=) = bind fOptional

testOptional2 = some 5 >>= \a ->
                nil    >>= \b ->
                some 6 >>= \c ->
                yield $ a * c
    where (>>=) = bind fOptional

Try it out for yourself to see the results.