This might be the least interesting article title on the Internet. However, it is something I have been looking into as I work on my language, psilo.

So I have a few overlapping concerns:

psilo, like Haskell, doesn't semantically support imperative programming (ie, recipe-style "statement; statement; ..." programming). However, I'm not a sadist: I want the programmer to be able to write more intuitive programs if she can

*earn it*.I'm a fan of the free monad pattern in Haskell but I don't want to support typeclasses. Thus I am interested in implementing free monad infrastructure using nothing but algebraic data types.

Since delimited continuations are tantamount to monads, I want the user to be able to write what amounts to an abstract syntax tree type and a few functions in continuation passing style and in return receive a monad,

`do`

notation, and composable imperative programming constructs.

This post is a simple exploration of implementing the `Functor`

typeclass as an algebraic data type, and then deriving a free monad from it.

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

For kicks I have re-written the `sequence`

function available in Haskell. psilo will essentially use this or an equivalent function to implement `do`

notation under the covers.

# 2 An example: re-creating the `Maybe`

monad.

Apple's Swift programming language seems to have ignited more widespread interest in optional types. So, just to show there is nothing up my sleeves, I am re-creating the `Maybe`

monad with the name `Optional`

.

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