# Combining free monads in F# by Mark Seemann

*An example of how to compose free monads in F#.*

This article is an instalment in a series of articles about modelling long-running interactions with pure, functional code. In the previous article, you saw how to combine a pure command-line API with an HTTP-client API in Haskell. In this article, you'll see how to translate the Haskell proof of concept to F#.

### HTTP API client module #

You've already seen how to model command-line interactions as pure code in a previous article. You can define interactions with the online restaurant reservation HTTP API in the same way. First, define some types required for input and output to the API:

type Slot = { Date : DateTimeOffset; SeatsLeft : int } type Reservation = { Date : DateTimeOffset Name : string Email : string Quantity : int }

The `Slot`

type contains information about how many available seats are left on a particular date. The `Reservation`

type contains the information required in order to make a reservation. It's the same `Reservation`

F# record type you saw in a previous article, but now it's moved here.

The online restaurant reservation HTTP API may afford more functionality than you need, but there's no reason to model more instructions than required:

type ReservationsApiInstruction<'a> = | GetSlots of (DateTimeOffset * (Slot list -> 'a)) | PostReservation of Reservation * 'a

This instruction set models two interactions. The `GetSlots`

case models an instruction to request, from the HTTP API, the slots for a particular date. The `PostReservation`

case models an instruction to make a POST HTTP request with a `Reservation`

, thereby making a reservation.

While Haskell can automatically make this type a `Functor`

, in F# you have to write the code yourself:

// ('a -> 'b) -> ReservationsApiInstruction<'a> // -> ReservationsApiInstruction<'b> let private mapI f = function | GetSlots (x, next) -> GetSlots (x, next >> f) | PostReservation (x, next) -> PostReservation (x, next |> f)

This turns `ReservationsApiInstruction<'a>`

into a functor, which is, however, not the ultimate goal. The final objective is to enable syntactic sugar, so that you can write pure `ReservationsApiInstruction<'a>`

Abstract Syntax Trees (ASTs) in standard F# syntax. In order to fulfil that ambition, you need a computation expression builder, and to create one of those, you need a monad.

You can turn `ReservationsApiInstruction<'a>`

into a monad using the free monad recipe that you've already seen. Creating a free monad, however, involves adding another type that will become both monad and functor, so I deliberately make `mapI`

private in order to prevent confusion. This is also the reason I didn't name the function `map`

: you'll need that name for a different type. The *I* in `mapI`

stands for *instruction*.

The `mapI`

function pattern-matches on the (implicit) `ReservationsApiInstruction`

argument. In the `GetSlots`

case, it returns a new `GetSlots`

value, but composes the `next`

continuation with `f`

. In the `PostReservation`

case, it returns a new `PostReservation`

value, but pipes `next`

to `f`

. The reason for the difference is that `PostReservation`

is degenerate: `next`

isn't a function, but a value.

Now that `ReservationsApiInstruction<'a>`

is a functor, you can create a free monad from it. The first step is to introduce a new type for the monad:

type ReservationsApiProgram<'a> = | Free of ReservationsApiInstruction<ReservationsApiProgram<'a>> | Pure of 'a

This is a recursive type that enables you to assemble ASTs that ultimately can return a value. The `Pure`

case enables you to return a value, while the `Free`

case lets you describe what should happen next.

Using `mapI`

, you can make a monad out of `ReservationsApiProgram<'a>`

by adding a `bind`

function:

// ('a -> ReservationsApiProgram<'b>) -> ReservationsApiProgram<'a> // -> ReservationsApiProgram<'b> let rec bind f = function | Free instruction -> instruction |> mapI (bind f) |> Free | Pure x -> f x

If you refer back to the `bind`

implementation for `CommandLineProgram<'a>`

, you'll see that *it's the exact same code*. In Haskell, creating a free monad from a functor is automatic. In F#, it's boilerplate.

Likewise, you can make `ReservationsApiProgram<'a>`

a functor:

// ('a -> 'b) -> ReservationsApiProgram<'a> -> ReservationsApiProgram<'b> let map f = bind (f >> Pure)

Again, this is the same code as in the `CommandLine`

module. You can copy and paste it. It is, however, not the same function, because the types are different.

Finally, to round off the reservations HTTP client API, you can supply functions that lift instructions to programs:

// DateTimeOffset -> ReservationsApiProgram<Slot list> let getSlots date = Free (GetSlots (date, Pure)) // Reservation -> ReservationsApiProgram<unit> let postReservation r = Free (PostReservation (r, Pure ()))

That's everything you need to create a small computation expression builder:

type ReservationsApiBuilder () = member this.Bind (x, f) = ReservationsApi.bind f x member this.Return x = Pure x member this.ReturnFrom x = x member this.Zero () = Pure ()

Create an instance of the `ReservationsApiBuilder`

class in order to use `reservationsApi`

computation expressions:

let reservationsApi = ReservationsApiBuilder ()

This, in total, defines a pure API for interacting with the online restaurant reservation system, including all the syntactic sugar you'll need to stay sane. As usual, some boilerplate code is required, but I'm not too worried about its maintenance overhead, as it's unlikely to change much, once you've added it. If you've followed the recipe, the API obeys the category, functor, and monad laws, so it's not something you've invented; it's an instance of a universal abstraction.

### Monad stack #

The addition of the above `ReservationsApi`

module is only a step towards the overall goal, which is to write a command-line wizard you can use to make reservations against the online API. In order to do so, you must combine the two monads `CommandLineProgram<'a>`

and `ReservationsApiProgram<'a>`

. In Haskell, you get that combination for free via the built-in generic `FreeT`

type, which enables you to stack monads. In F#, you have to explicitly declare the type:

type CommandLineReservationsApiT<'a> = | Run of CommandLineProgram<ReservationsApiProgram<'a>>

This is a single-case discriminated union that stacks `ReservationsApiProgram`

and `CommandLineProgram`

. In this incarnation, it defines a single case called `Run`

. The reason for this is that it enables you to follow the free monad recipe without having to do much thinking. Later, you'll see that it's possible to simplify the type.

The naming is inspired by Haskell. This type is a piece of the puzzle corresponding to Haskell's `FreeT`

type. The *T* in `FreeT`

stands for *transformer*, because `FreeT`

is actually something called a *monad transformer*. That's not terribly important in an F# context, but that's the reason I also tagged on the *T* in `CommandLineReservationsApiT<'a>`

.

`FreeT`

is actually only a 'wrapper' around another monad. In order to extract the contained monad, you can use a function called `runFreeT`

. That's the reason I called the F# case `Run`

.

You can easily make your stack of monads a functor:

// ('a -> 'b) -> CommandLineProgram<ReservationsApiProgram<'a>> // -> CommandLineProgram<ReservationsApiProgram<'b>> let private mapStack f x = commandLine { let! x' = x return ReservationsApi.map f x' }

The `mapStack`

function uses the `commandLine`

computation expression to access the `ReservationsApiProgram`

contained within the `CommandLineProgram`

. Thanks to the `let!`

binding, `x'`

is a `ReservationsApiProgram<'a>`

value. You can use `ReservationsApi.map`

to map `x'`

with `f`

.

It's now trivial to make `CommandLineReservationsApiT<'a>`

a functor as well:

// ('a -> 'b) -> CommandLineReservationsApiT<'a> // -> CommandLineReservationsApiT<'b> let private mapT f (Run p) = mapStack f p |> Run

The `mapT`

function simply pattern-matches the monad stack out of the `Run`

case, calls `mapStack`

, and pipes the return value into another `Run`

case.

By now, it's should be fairly clear that we're following the same recipe as before. You have a functor; make a monad out of it. First, define a type for the monad:

type CommandLineReservationsApiProgram<'a> = | Free of CommandLineReservationsApiT<CommandLineReservationsApiProgram<'a>> | Pure of 'a

Then add a `bind`

function:

// ('a -> CommandLineReservationsApiProgram<'b>) // -> CommandLineReservationsApiProgram<'a> // -> CommandLineReservationsApiProgram<'b> let rec bind f = function | Free instruction -> instruction |> mapT (bind f) |> Free | Pure x -> f x

This is almost the same code as the above `bind`

function for `ReservationsApi`

. The only difference is that the underlying map function is named `mapT`

instead of `mapI`

. The types involved, however, are different.

You can also add a `map`

function:

// ('a -> 'b) -> (CommandLineReservationsApiProgram<'a> // -> CommandLineReservationsApiProgram<'b>) let map f = bind (f >> Pure)

This is another copy-and-paste job. Such repeatable. Wow.

When you create a monad stack, you need a way to lift values from each of the constituent monads up to the combined monad. In Haskell, this is done with the `lift`

and `liftF`

functions, but in F#, you must explicitly add such functions:

// CommandLineProgram<ReservationsApiProgram<'a>> // -> CommandLineReservationsApiProgram<'a> let private wrap x = x |> Run |> mapT Pure |> Free // CommandLineProgram<'a> -> CommandLineReservationsApiProgram<'a> let liftCL x = wrap <| CommandLine.map ReservationsApiProgram.Pure x // ReservationsApiProgram<'a> -> CommandLineReservationsApiProgram<'a> let liftRA x = wrap <| CommandLineProgram.Pure x

The private `wrap`

function takes the underlying 'naked' monad stack (`CommandLineProgram<ReservationsApiProgram<'a>>`

) and turns it into a `CommandLineReservationsApiProgram<'a>`

value. It first wraps `x`

in `Run`

, which turns `x`

into a `CommandLineReservationsApiT<'a>`

value. By piping that value into `mapT Pure`

, you get a `CommandLineReservationsApiT<CommandLineReservationsApiProgram<'a>>`

value that you can finally pipe into `Free`

in order to produce a `CommandLineReservationsApiProgram<'a>`

value. Phew!

The `liftCL`

function lifts a `CommandLineProgram`

(*CL*) to `CommandLineReservationsApiProgram`

by first using `CommandLine.map`

to lift `x`

to a `CommandLineProgram<ReservationsApiProgram<'a>>`

value. It then pipes that value to `wrap`

.

Likewise, the `liftRA`

function lifts a `ReservationsApiProgram`

(*RA*) to `CommandLineReservationsApiProgram`

. It simply elevates `x`

to a `CommandLineProgram`

value by using `CommandLineProgram.Pure`

. Subsequently, it pipes that value to `wrap`

.

In both of these functions, I used the slightly unusual backwards pipe operator `<|`

. The reason for that is that it emphasises the similarity between `liftCL`

and `liftRA`

. This is easier to see if you remove the type comments:

let liftCL x = wrap <| CommandLine.map ReservationsApiProgram.Pure x let liftRA x = wrap <| CommandLineProgram.Pure x

This is how I normally write my F# code. I only add the type comments for the benefit of you, dear reader. Normally, when you have an IDE, you can always inspect the types using the built-in tools.

Using the backwards pipe operator makes it immediately clear that both functions depend in the `wrap`

function. This would have been muddied by use of the normal forward pipe operator:

let liftCL x = CommandLine.map ReservationsApiProgram.Pure x |> wrap let liftRA x = CommandLineProgram.Pure x |> wrap

The behaviour is the same, but now `wrap`

doesn't align, making it harder to discover the kinship between the two functions. My use of the backward pipe operator is motivated by readability concerns.

Following the free monad recipe, now create a computation expression builder:

type CommandLineReservationsApiBuilder () = member this.Bind (x, f) = CommandLineReservationsApi.bind f x member this.Return x = Pure x member this.ReturnFrom x = x member this.Zero () = Pure ()

Finally, create an instance of the class:

let commandLineReservationsApi = CommandLineReservationsApiBuilder ()

Putting the `commandLineReservationsApi`

value in a module will enable you to use it for computation expressions whenever you open that module. I normally put it in a module with the `[<AutoOpen>]`

attribute so that it automatically becomes available as soon as I open the containing namespace.

### Simplification #

While there *can* be good reasons to introduce single-case discriminated unions in your F# code, they're isomorphic with their contained type. (This means that there's a lossless conversion between the union type and the contained type, in both directions.) Following the free monad recipe, I introduced `CommandLineReservationsApiT`

as a discriminated union, but since it's a single-case union, you can refactor it to its contained type.

If you delete the `CommandLineReservationsApiT`

type, you'll first have to change the definition of the program type to this:

type CommandLineReservationsApiProgram<'a> = | Free of CommandLineProgram<ReservationsApiProgram<CommandLineReservationsApiProgram<'a>>> | Pure of 'a

You simply replace `CommandLineReservationsApiT<_>`

with `CommandLineProgram<ReservationsApiProgram<_>>`

, effectively promoting the type contained in the `Run`

case to be the container in the `Free`

case.

Once `CommandLineReservationsApiT`

is gone, you'll also need to delete the `mapT`

function, and amend `bind`

:

// ('a -> CommandLineReservationsApiProgram<'b>) // -> CommandLineReservationsApiProgram<'a> // -> CommandLineReservationsApiProgram<'b> let rec bind f = function | Free instruction -> instruction |> mapStack (bind f) |> Free | Pure x -> f x

Likewise, you must also adjust the `wrap`

function:

let private wrap x = x |> mapStack Pure |> Free

The rest of the above code stays the same.

### Wizard #

In Haskell, you get combinations of monads for free via the `FreeT`

type, whereas in F#, you have to work for it. Once you have the combination in monadic form as well, you can write programs with that combination. Here's the wizard that collects your data and attempts to make a restaurant reservation on your behalf:

// CommandLineReservationsApiProgram<unit> let tryReserve = commandLineReservationsApi { let! count = liftCL readQuantity let! date = liftCL readDate let! availableSeats = ReservationsApi.getSlots date |> ReservationsApi.map (List.sumBy (fun slot -> slot.SeatsLeft)) |> liftRA if availableSeats < count then do! sprintf "Only %i remaining seats." availableSeats |> CommandLine.writeLine |> liftCL else let! name = liftCL readName let! email = liftCL readEmail do! { Date = date; Name = name; Email = email; Quantity = count } |> ReservationsApi.postReservation |> liftRA }

Notice that `tryReserve`

is a *value*, and not a function. It's a pure value that contains an AST - a small program that describes the impure interactions that you'd like to take place. It's defined entirely within a `commandLineReservationsApi`

computation expression.

It starts by using the `readQuantity`

and `readDate`

program values you saw in the previous F# article. Both of these values are `CommandLineProgram`

values, so you have to use `liftCL`

to lift them to `CommandLineReservationsApiProgram`

values - only then can you `let!`

bind them to an `int`

and a `DateTimeOffset`

, respectively. This is just like the use of `lift`

in the previous article's Haskell example.

Once the program has collected the desired `date`

from the user, it calls `ReservationsApi.getSlots`

and calculates the sum over all the returned `SeatsLeft`

labels. The `ReservationsApi.getSlots`

function returns a `ReservationsApiProgram<Slot list>`

, the `ReservationsApi.map`

turns it into a `ReservationsApiProgram<int>`

value that you must `liftRA`

in order to be able to `let!`

bind it to an `int`

value. Let me stress once again: the program actually doesn't *do* any of that; it constructs an AST with instructions to that effect.

If it turns out that there's too few seats left, the program writes that on the command line and exits. Otherwise, it continues to collect the user's name and email address. That's all the data required to create a `Reservation`

record and pipe it to `ReservationsApi.postReservation`

.

### Interpreters #

The `tryReserve`

wizard is a pure value. It contains an AST that can be interpreted in such a way that impure operations happen. You've already seen the `CommandLineProgram`

interpreter in a previous article, so I'm not going to repeat it here. I'll only note that I renamed it to `interpretCommandLine`

because I want to use the name `interpret`

for the combined interpreter.

The interpreter for `ReservationsApiProgram`

values is similar to the `CommandLineProgram`

interpreter:

// ReservationsApiProgram<'a> -> 'a let rec interpretReservationsApi = function | ReservationsApiProgram.Pure x -> x | ReservationsApiProgram.Free (GetSlots (d, next)) -> ReservationHttpClient.getSlots d |> Async.RunSynchronously |> next |> interpretReservationsApi | ReservationsApiProgram.Free (PostReservation (r, next)) -> ReservationHttpClient.postReservation r |> Async.RunSynchronously next |> interpretReservationsApi

The `interpretReservationsApi`

function pattern-matches on its (implicit) `ReservationsApiProgram`

argument, and performs the appropriate actions according to each instruction. In all `Free`

cases, it delegates to implementations defined in a `ReservationHttpClient`

module. The code in that module isn't shown here, but you can see it in the GitHub repository that accompanies this article.

You can combine the two 'leaf' interpreters in an interpreter of `CommandLineReservationsApiProgram`

values:

// CommandLineReservationsApiProgram<'a> -> 'a let rec interpret = function | CommandLineReservationsApiProgram.Pure x -> x | CommandLineReservationsApiProgram.Free p -> p |> interpretCommandLine |> interpretReservationsApi |> interpret

As usual, in the `Pure`

case, it simply returns the contained value. In the `Free`

case, `p`

is a `CommandLineProgram<ReservationsApiProgram<CommandLineReservationsApiProgram<'a>>>`

. Since it's a `CommandLineProgram`

value, you can interpret it with `interpretCommandLine`

, which returns a `ReservationsApiProgram<CommandLineReservationsApiProgram<'a>>`

. Since that's a `ReservationsApiProgram`

, you can pipe it to `interpretReservationsApi`

, which then returns a `CommandLineReservationsApiProgram<'a>`

. An interpreter exists for that type as well, namely the `interpret`

function itself, so recursively invoke it again. In other words, `interpret`

will keep recursing until it hits a `Pure`

case.

### Execution #

Everything is now in place so that you can execute your program. This is the program's entry point:

[<EntryPoint>] let main _ = interpret Wizard.tryReserve 0 // return an integer exit code

When you run it, you'll be able to have an interaction like this:

Please enter number of diners: 4 Please enter your desired date: 2017-11-25 Please enter your name: Mark Seemann Please enter your email address: mark@example.net OK

If you want to run this code sample yourself, you're going to need an appropriate HTTP API with which you can interact. I hosted the API on my local machine, and afterwards verified that the record was, indeed, written in the reservations database.

### Summary #

As expected, you can combine free monads in F#, although it requires more boilerplate code than in Haskell.

**Next:** F# free monad recipe.