Monads for free in F#

#functional #dotnet #fsharp

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

// ('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:

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

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

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:

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

/// 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.¹

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

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:

/// ('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:

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:

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

/// 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):

/// 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 (Haskell)
F# free monad recipe

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