F# free monad recipe by Mark Seemann
How to create free monads in F#.
This is not a design pattern, but it's something related. Let's call it a recipe. A design pattern should, in my opinion, be fairly languageagnostic (although hardly universally applicable). This article, on the contrary, specifically addresses a problem in F#:
How do you create a free monad in F#?
By following the present recipe.
The recipe here is a stepbystep process, but be sure to first read the sections on motivation and when to use it. A free monads isn't a goal in itself.
This article doesn't attempt to explain the details of free monads, but instead serve as a reference. For an introduction to free monads, I think my article Pure times is a good place to start. See also the Motivating examples section, below.
Motivation
A frequently asked question about F# is: what's the F# equivalent to an interface? There's no single answer to this question, because, as always, It Depends™. Why do you need an interface in the first place? What is its intended use?
Sometimes, in OOP, an interface can be used for a Strategy. This enables you to dynamically replace or select between different (sub)algorithms at runtime. If the algorithm is pure, then an idiomatic F# equivalent would be a function.
At other times, though, the person asking the question has Dependency Injection in mind. In OOP, dependencies are often modelled as interfaces with several members. Such dependencies are systematically impure, and thereby not part of functional design. If at all possible, prefer impure/pure/impure sandwiches over interactions. Sometimes, however, you'll need something that works like an interface or abstract base class. Free monads can address such situations.
In general, a free monad allows you to build a monad from any functor, but why would you want to do that? The most common reason I've encountered is exactly in order to model impure interactions in a pure manner; in other words: Dependency Injection.
Refactor interface to functor
This recipe comes in three parts:
 A recipe for refactoring interfaces to a functor.
 The core recipe for creating a monad from any functor.
 A recipe for adding an interpreter.
Imagine that you have an interface that you'd like to refactor. In C# it might look like this:
public interface IFace { Out1 Member1(In1 input); Out2 Member2(In2 input); }
In F#, it'd look like this:
type IFace = abstract member Member1 : input:In1 > Out1 abstract member Member2 : input:In2 > Out2
I've deliberately kept the interface vague and abstract in order to showcase the recipe instead of a particular example. For realistic examples, refer to the examples section, further down.
To refactor such an interface to a functor, do the following:
 Create a discriminated union. Name it after the interface name, but append the word instruction as a suffix.
 Make the union type generic.

For each member in the interface, add a case.
 Name the case after the name of the member.
 Declare the type of data contained in the case as a pair (a twoelement tuple).
 Declare the type of the first element in that tuple as the type of the input argument(s) to the interface member. If the member has more than one input argument, declare it as a (nested) tuple.
 Declare the type of the second element in the tuple as a function. The input type of that function should be the output type of the original interface member, and the output type of the function should be the generic type argument for the union type.
 Add a map function for the union type. I'd recommend making this function private and avoid naming it
map
in order to prevent naming conflicts. I usually name this functionmapI
, where the I stands for instruction.  The map function should take a function of the type
'a > 'b
as its first (curried) argument, and a value of the union type as its second argument. It should return a value of the union type, but with the generic type argument changed from'a
to'b
.  For each case in the union type, map it to a value of the same case. Copy the (nongeneric) first element of the pair over without modification, but compose the function in the second element with the input function to the map function.
type FaceInstruction<'a> =  Member1 of (In1 * (Out1 > 'a))  Member2 of (In2 * (Out2 > 'a))
The map function becomes:
// ('a > 'b) > FaceInstruction<'a> > FaceInstruction<'b> let private mapI f = function  Member1 (x, next) > Member1 (x, next >> f)  Member2 (x, next) > Member2 (x, next >> f)
Such a combination of union type and map function satisfies the functor laws, so that's how you refactor an interface to a functor.
Free monad recipe
Given any functor, you can create a monad. The monad will be a new type that contains the functor; you will not be turning the functor itself into a monad. (Some functors can be turned into monads themselves, but if that's the case, you don't need to create a free monad.)
The recipe for turning any functor into a monad is as follows:
 Create a generic discriminated union. You can name it after the underlying functor, but append a suffix such as Program. In the following, this is called the 'program' union type.
 Add two cases to the union:
Free
andPure
.  The
Free
case should contain a single value of the contained functor, generically typed to the 'program' union type itself. This is a recursive type definition.  The
Pure
case should contain a single value of the union's generic type.  Add a
bind
function for the new union type. The function should take two arguments:  The first argument to the
bind
function should be a function that takes the generic type argument as input, and returns a value of the 'program' union type as output. In the rest of this recipe, this function is calledf
.  The second argument to the
bind
function should be a 'program' union type value.  The return type of the
bind
function should be a 'program' union type value, with the same generic type as the return type of the first argument (f
).  Declare the
bind
function as recursive by adding therec
keyword.  Implement the
bind
function by patternmatching on theFree
andPure
cases:  In the
Free
case, pipe the contained functor value to the functor's map function, usingbind f
as the mapper function; then pipe the result of that toFree
.  In the
Pure
case, returnf x
, wherex
is the value contained in thePure
case.  Add a computation expression builder, using
bind
forBind
andPure
forReturn
.
type FaceProgram<'a> =  Free of FaceInstruction<FaceProgram<'a>>  Pure of 'a
It's worth noting that the Pure
case always looks like that. While it doesn't take much effort to write it, you could copy and paste it from another free monad, and no changes would be required.
According to the recipe, the bind
function should be implemented like this:
// ('a > FaceProgram<'b>) > FaceProgram<'a> > FaceProgram<'b> let rec bind f = function  Free x > x > mapI (bind f) > Free  Pure x > f x
Apart from one small detail, the bind
function always looks like that, so you can often copy and paste it from here and use it in your code, if you will. The only variation is that the underlying functor's map function isn't guaranteed to be called mapI
 but if it is, you can use the above bind
function as is. No modifications will be necessary.
In F#, a monad is rarely a goal in itself, but once you have a monad, you can add a computation expression builder:
type FaceBuilder () = member this.Bind (x, f) = bind f x member this.Return x = Pure x member this.ReturnFrom x = x member this.Zero () = Pure ()
While you could add more members (such as Combine
, For
, TryFinally
, and so on), I find that usually, those four methods are all I need.
Create an instance of the builder object, and you can start writing computation expressions:
let face = FaceBuilder ()
Finally, as an optional step, if you've refactored an interface to an instruction set, you can add convenience functions that lift each instruction case to the free monad type:
 For each case, add a function of the same name, but camelCased instead of PascalCased.
 Each function should have input arguments that correspond to the first element of the case's contained tuple (i.e. the input argument for the original interface). I usually prefer the arguments in curried form, but that's not a requirement.
 Each function should return the corresponding instruction union case inside of the
Free
case. The case constructor must be invoked with the pair of data it requires. Populate the first element with values from the input arguments to the convenience function. The second element should be thePure
case constructor, passed as a function.
FaceInstruction<'a>
:
// In1 > FaceProgram<Out1> let member1 in1 = Free (Member1 (in1, Pure)) // In2 > FaceProgram<Out2> let member2 in2 = Free (Member2 (in2, Pure))
Such functions are conveniences that make it easier to express what the underlying functor expresses, but in the context of the free monad.
Interpreters
A free monad is a recursive type, and values are trees. The leafs are the Pure
values. Often (if not always), the point of a free monad is to evaluate the tree in order to pull the leaf values out of it. In order to do that, you must add an interpreter. This is a function that recursively patternmatches over the free monad value until it encounters a Pure
case.
At least in the case where you've refactored an interface to a functor, writing an interpreter also follows a recipe. This is equivalent to writing a concrete class that implements an interface.
 For each case in the instructionset functor, write an implementation function that takes the case's 'input' tuple element type as input, and returns a value of the type used in the case's second tuple element. Recall that the second element in the pair is a function; the output type of the implementation function should be the input type for that function.
 Add a function to implement the interpreter; I often call it
interpret
. Make it recursive by adding therec
keyword.  Patternmatch on
Pure
and each case contained inFree
.  In the
Pure
case, simply return the value contained in the case.  In the
Free
case, patternmatch the underlying pair out if each of the instructionset functor's cases. The first element of that tuple is the 'input value'. Pipe that value to the corresponding implementation function, pipe the return value of that to the function contained in the second element of the tuple, and pipe the result of that recursively to the interpreter function.
imp1
and imp2
exist. According to the recipe, imp1
has the type In1 > Out1
, and imp2
has the type In2 > Out2
. Given these functions, the running example becomes:
// FaceProgram<'a> > 'a let rec interpret = function  Pure x > x  Free (Member1 (x, next)) > x > imp1 > next > interpret  Free (Member2 (x, next)) > x > imp2 > next > interpret
The Pure
case always looks like that. Each of the Free
cases use a different implementation function, but apart from that, they are, as you can tell, the spitting image of each other.
Interpreters like this are often impure because the implementation functions are impure. Nothing prevents you from defining pure interpreters, although they often have limited use. They do have their place in unit testing, though.
// Out1 > Out2 > FaceProgram<'a> > 'a let rec interpretStub out1 out2 = function  Pure x > x  Free (Member1 (_, next)) > out1 > next > interpretStub out1 out2  Free (Member2 (_, next)) > out2 > next > interpretStub out1 out2
This interpreter effectively ignores the input value contained within each Free
case, and instead uses the pure values out1
and out2
. This is essentially a Stub  an 'implementation' that always returns predefined values.
The point is that you can have more than a single interpreter, pure or impure, just like you can have more than one implementation of an interface.
When to use it
Free monads are often used instead of Dependency Injection. Note, however, that while the free monad values themselves are pure, they imply impure behaviour. In my opinion, the main benefit of pure code is that, as a code reader and maintainer, I don't have to worry about sideeffects if I know that the code is pure. With a free monad, I do have to worry about sideeffects, because, although the ASTs are pure, an impure interpreter will cause sideeffects to happen. At least, however, the sideeffects are known; they're restricted to a small subset of operations. Haskell enforces this distinction, but F# doesn't. The question, then, is how valuable you find this sort of design.
I think it still has some value, because a free monad explicitly communicates an intent of doing something impure. This intent becomes encoded in the types in your code base, there for all to see. Just as I prefer that functions return 'a option
values if they may fail to produce a value, I like that I can tell from a function's return type that a delimited set of impure operations may result.
Clearly, creating free monads in F# requires some boilerplate code. I hope that this article has demonstrated that writing that boilerplate code isn't difficult  just follow the recipe. You almost don't have to think. Since a monad is a universal abstraction, once you've written the code, it's unlikely that you'll need to deal with it much in the future. After all, mathematical abstractions don't change.
Perhaps a more significant concern is how familiar free monads are to developers of a particular code base. Depending on your position, you could argue that free monads come with high cognitive overhead, or that they specifically lower the cognitive overhead.
Insights are obscure until you grasp them; after that, they become clear.
This applies to free monads as well. You have to put effort into understanding them, but once you do, you realise that they are more than a pattern. They are universal abstractions, governed by laws. Once you grok free monads, their cognitive load wane.
Consider, then, the developers who will be interacting with the free monad. If they already know free monads, or have enough of a grasp of monads that this might be their next step, then using free monads could be beneficial. On the other hand, if most developers are new to F# or functional programming, free monads should probably be avoided for the time being.
This flowchart summarises the above reflections:
Your first consideration should be whether your context enables an impure/pure/impure sandwich. If so, there's no reason to make things more complicated than they have to be. To use Fred Brooks' terminology, this should go a long way to avoid accidental complexity.
If you can't avoid longrunning, impure interactions, then consider whether purity, or strictly functional design, is important to you. F# is a multiparadigmatic language, and it's perfectly possible to write code that's impure, yet still wellstructured. You can use partial application as an idiomatic alternative to Dependency Injection.
If you prefer to keep your code functional and explicit, you may consider using free monads. In this case, I still think you should consider the maintainers of the code base in question. If everyone involved are comfortable with free monads, or willing to learn, then I believe it's a viable option. Otherwise, I'd recommend falling back to partial application, even though Dependency Injection makes everything impure.
Motivating examples
The strongest motivation, I believe, for introducing free monads into a code base is to model longrunning, impure interactions in a functional style.
Like most other software design considerations, the overall purpose of application architecture is to deal with (essential) complexity. Thus, any example must be complex enough to warrant the design. There's little point in a Dependency Injection hello world example in C#. Likewise, a hello world example using free monads hardly seems justified. For that reason, examples are provided in separate articles.
A good place to start, I believe, is with the small Pure times article series. These articles show how to address a particular, authentic problem using strictly functional programming. The focus of these articles is on problemsolving, so they sometimes omit detailed explanations in order to keep the narrative moving.
If you need detailed explanations about all elements of free monads in F#, the present article series offers just that, particularly the Hello, pure commandline interaction article.
Variations
The above recipes describe the regular scenario. Variations are possible. Obviously, you can choose different naming strategies and so on, but I'm not going to cover this in greater detail.
There are, however, various degenerate cases that deserve a few words. An interaction may return no data, or take no input. In F#, you can always model the lack of data as unit
(()
), so it's definitely possible to define an instruction case like Foo of (unit * Out1 > 'a)
, or Bar of (In2 * unit > 'a)
, but since unit
doesn't contain any data, you can remove it without changing the abstraction.
The Hello, pure commandline interaction article contains a single type that exemplifies both degenerate cases. It defines this instruction set:
type CommandLineInstruction<'a> =  ReadLine of (string > 'a)  WriteLine of string * 'a
The ReadLine
case takes no input, so instead of containing a pair of input and continuation, this case contains only the continuation function. Likewise, the WriteLine
case is also degenerate, but here, there's no output. This case does contain a pair, but the second element isn't a function, but a value.
This has some superficial consequences for the implementation of functor and monad functions. For example, the mapI
function becomes:
// ('a > 'b) > CommandLineInstruction<'a> > CommandLineInstruction<'b> let private mapI f = function  ReadLine next > ReadLine (next >> f)  WriteLine (x, next) > WriteLine (x, next > f)
Notice that in the ReadLine
case, there's no tuple on which to patternmatch. Instead, you can directly access next
.
In the WriteLine
case, the return value changes from function composition (next >> f
) to a regular function call (next > f
, which is equivalent to f next
).
The lift functions also change:
// CommandLineProgram<string> let readLine = Free (ReadLine Pure) // string > CommandLineProgram<unit> let writeLine s = Free (WriteLine (s, Pure ()))
Since there's no input, readLine
degenerates to a value, instead of a function. On the other hand, while writeLine
remains a function, you'll have to pass a value (Pure ()
) as the second element of the pair, instead of the regular function (Pure
).
Apart from such minor changes, the omission of unit
values for input or output has little significance.
Another variation from the above recipe that you may see relates to interpreters. In the above recipe, I described how, for each instruction, you should create an implementation function. Sometimes, however, that function is only a few lines of code. When that happens, I occasionally inline the function directly in the interpreter. Once more, the CommandLineProgram
API provides an example:
// CommandLineProgram<'a> > 'a let rec interpret = function  Pure x > x  Free (ReadLine next) > Console.ReadLine () > next > interpret  Free (WriteLine (s, next)) > Console.WriteLine s next > interpret
Here, no custom implementation functions are required, because Console.ReadLine
and Console.WriteLine
already exist and serve the desired purpose.
Summary
This article describes a repeatable, and automatable, process for refactoring an interface to a free monad. I've done this enough times now that I believe that this process is always possible, but I have no formal proof for this.
I also strongly suspect that the reverse process is possible. For any instruction set elevated to a free monad, I think you should be able to define an objectoriented interface. If this is true, then objectoriented interfaces and ASTbased free monads are isomorphic.