Monads for free in F#
Tags: functional, dotnet, fsharp
Published: 2020-05-01 05:57:16

If you dabble in Haskell or category theory, you might have heard of "free monads". But what exactly is a free monad, and can the concept be translated to F#? I'm going to answer those questions by creating a simple free monad, step by step. The resulting code won't actually be useful for much itself, but it provides a foundation that we can build on later.

I'm going to assume that you're already familiar with two important concepts in functional programming:

* **Functors**. A [functor](https://dev.to/shimmer/functors-in-f-2fd7) is a type that can be "mapped" over. In F#, this usually means that the corresponding module contains a `map` function, like `List.map` or `Array.map`.

* **Monads**. A [monad](https://fsharpforfunandprofit.com/posts/elevated-world/) is a type that can be used to build computations (a.k.a. workflows). This means that the type supports some sort of `bind` function, although it doesn't always go by that name.

Every monad is a functor, but not every functor is a monad. However, it turns out that if you have a functor type, you can **always** create a corresponding monad type, regardless of the details of how your functor works. It's a free monad!

# The Option type

F# options are functors, as witnessed by the `Option.map` function:

```fsharp
// ('a -> 'b) -> Option<'a> -> Option<'b>
let map f opt = function
    | Some x -> Some (f x)
    | None -> None
```

This works by applying the given mapping function `f` to the value contained by the option (if there is one). In other words, if we have a function that maps type `'a` to type `'b`, then we can use it to map type `Option<'a>` to type `Option<'b>`.

You are probably aware that `Option` is also a monad, as witnessed by its handy `Option.bind` function. However, in this article, we are not going to use that function. Instead, we're going to create an entirely separate `Option` monad (with very different behavior) using only `Option.map`.

# Nested functors

Because `Option` is a functor, it can be nested. For example, we can create values of type `Option<Option<int>>` or `Option<Option<Option<string>>>`. Any functor type can be nested in the same way. For example, `List<List<int>>` or `Array<Array<Array<string>>>`. Note that the concrete type depends on the number of nested levels. `Option<int>` is not the same type as `Option<Option<int>>`.

We would like to create a separate type that contains nested options, so that the concrete type is the same regardless of how many levels it contains. This sounds a bit like F#'s `List` type:

```fsharp
type List<'t> =
    | Cons of 't * List<'t>
    | Nil
```

Note that a list of integers always has type `List<int>`, regardless of its length:

```fsharp
let intListA : List<int> = Cons (1, Nil)             // [1]
let intListB : List<int> = Cons (2, Cons (3, Nil))   // [2; 3]
```

Let's use the same pattern to create a "nest" of options:

```fsharp
/// Free monad of Option<'t>.
type Nest<'t> =

    /// Nested options.
    | Free of Option<Nest<'t>>

    /// Lifts a value directly into the monad.
    | Pure of 't
```

Notice that `Nest` is a lot like `List`: `Free` corresponds to a cons cell, and `Pure` corresponds to the list terminator. The main difference in this case is that a nest of options can hold at most only a single value of `t`, in the `Pure` cell at the very end - unlike a list, which holds a value in every cons cell (and none at the end).

Also notice that this type refers to `Option` only once, in the recursive definition of the `Free` constructor. It would be nice if we could generalize `Nest` so that it didn't depend on `Option` at all, but F#'s type system is not strong enough for that (unlike Haskell's). Such a generic type might look something like this:

```fsharp
/// Free monad of 'functor<'t>.
type FreeMonad<'functor, 't> =

    /// Nested functors.
    | Free of 'functor<FreeMonad<'functor, 't>>   // oops - not legal F#

    /// Lifts a value directly into the monad.
    | Pure of 't
```

Since this isn't possible in F#, every time you want to create a free monad for a functor type, you'll have to write the whole thing out with at least one hardcoded reference to the functor type.[^1]

Anyway, we can use our new `Nest` type to create option nests like this:

```fsharp
let nestA = Pure 1
let nestB = Free (Some (Pure 2))
let nestC = Free (Some (Free (Some (Pure 3))))
let nestD = Free None
let nestE = Free (Some (Free None))
```

All of these have (or can have) the same type, `Nest<int>`.

# The free monad

We now have a type that represents nested options, so next we need to show that it actually is a monad. This means creating a `bind` function that can connect two nests using only the fact that `Option` is a functor:

```fsharp
/// ('a -> Nest<'b>) -> Nest<'a> -> Nest<'b>
let rec bind f = function
    | Free opt ->
        opt
            |> Option.map (bind f)
            |> Free
    | Pure value -> f value
```

This is the heart of the free monad, so it's worth walking through what's happening in detail. The important thing to understand about the `Free` case is that `bind f` is a function of type `Nest<'a> -> Nest<'b>`, which is a mapping function for nests. The only thing we're allowed to know about `Option` is that it's a functor, so the only thing we can really do here is recursively pass the mapping function to the `Free` cell's contained option via `Option.map`. All we're really doing is handing off responsibility for the binding to the next nested level, which in turn hands it off to the next level, and so on, until we get to the bottom, which is either a `Pure` cell or a `None` option. We then construct a new `Free` cell from the resulting nest option. The `Pure` case at the end of the chain is the only place where we actually apply the binder function.

Note that `bind` depends on `Option` in only one way: the call to `Option.map`. We could change the implementation to work for another functor by simply invoking that functor's `map` function instead at the same location. None of the rest of `bind`'s code would have to change at all (although we should also rename the `opt` variable to something more appropriate for our other functor).

Now that we have a `bind` function, we can create a workflow builder:

```fsharp
type NestBuilder() =
    member __.Bind(nest, func) = nest |> Nest.bind func
    member __.Return(value) = Pure value
    member __.ReturnFrom(nest) = nest

let nest = NestBuilder()
```

To make computation expressions easy to write, we use a small utility function that lifts a given value into the monad as a two-level nest:

```fsharp
/// e.g. some "A' -> Free (Some (Pure "A"))
let some value =
    value |> Pure |> Some |> Free
```

We can use the builder to nest values as deeply as we want, without needing multiple levels of nested parentheses:

```fsharp
/// Free (Some (Free (Some (Free (Some (Pure "ABC"))))))
let example1 =
    nest {
        let! a = some "A"
        let! b = some (a + "B")
        return! some (b + "C")
    }
```

In this example, I've chosen to concatenate strings in the binder function, but we could do anything else we want instead.

If we run into a `None` option at any point, the nesting process simply stops (because `Option.map (bind f)` returns `None` without recursively invoking `bind`):

```fsharp
/// Free (Some (Free (Some (Free None))))
let example2 =
    nest {
        let! a = some "A"
        let! b = some (a + "B")
        do! Free None
        return! some (b + "C")   // b + "C" never happens
    }
```

# Conclusion

So what's the point of creating nested options this way? There's really no practical value at all, because we don't have any need to conceptualize nested options as a kind of list. I only chose `Option` because it is one of the simplest non-trivial functors. However, there are other functors where nesting can usefully be thought of as representing a list, and that's where free monads shine.

For more information on the free monad, you might find these articles useful:
* [Why free monads matter](http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html) (Haskell)
* [F# free monad recipe](https://blog.ploeh.dk/2017/08/07/f-free-monad-recipe/)


[^1]: In practice, you'll often want additional constructors, and multiple type parameters, all of which follow the same general pattern. We're not going to cover that here.