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, likeList.map
orArray.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.1
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. ↩
Top comments (2)
Good point. I'm surprised that
map
doesn't follow that pattern in Ruby.You can’t destructure a key/value pair directly?