# Deriving free monads from value-level functors

Or, I have finally cured insomnia. Call CNN.

# 1 Functors and Free Monads

An instance of **F** should contain a function called `_map`

constrained by whichever base type is being functor-ized.

`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.

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.

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

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`

.

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