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.
