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 language-agnostic (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 step-by-step 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 run-time. 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:

  1. A recipe for refactoring interfaces to a functor.
  2. The core recipe for creating a monad from any functor.
  3. A recipe for adding an interpreter.
The universal recipe for creating a monad from any functor follows in a later section. In this section, you'll see how to refactor an interface to a functor.

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:

  1. Create a discriminated union. Name it after the interface name, but append the word instruction as a suffix.
  2. Make the union type generic.
  3. For each member in the interface, add a case.
    1. Name the case after the name of the member.
    2. Declare the type of data contained in the case as a pair (a two-element tuple).
    3. 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.
    4. 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.
  4. 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 function mapI, where the I stands for instruction.
  5. 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.
  6. For each case in the union type, map it to a value of the same case. Copy the (non-generic) first element of the pair over without modification, but compose the function in the second element with the input function to the map function.
Following that recipe, the above interface becomes this union type:

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:

  1. 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.
  2. Add two cases to the union: Free and Pure.
  3. 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.
  4. The Pure case should contain a single value of the union's generic type.
  5. Add a bind function for the new union type. The function should take two arguments:
  6. 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 called f.
  7. The second argument to the bind function should be a 'program' union type value.
  8. 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).
  9. Declare the bind function as recursive by adding the rec keyword.
  10. Implement the bind function by pattern-matching on the Free and Pure cases:
  11. In the Free case, pipe the contained functor value to the functor's map function, using bind f as the mapper function; then pipe the result of that to Free.
  12. In the Pure case, return f x, where x is the value contained in the Pure case.
  13. Add a computation expression builder, using bind for Bind and Pure for Return.
Continuing the above example, the 'program' union type becomes:

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 = functionFree x -> x |> mapI (bind f) |> FreePure 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:

  1. For each case, add a function of the same name, but camelCased instead of PascalCased.
  2. 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.
  3. 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 the Pure case constructor, passed as a function.
In the current example, that would be two functions, one for each case of 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 pattern-matches 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.

  1. For each case in the instruction-set 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.
  2. Add a function to implement the interpreter; I often call it interpret. Make it recursive by adding the rec keyword.
  3. Pattern-match on Pure and each case contained in Free.
  4. In the Pure case, simply return the value contained in the case.
  5. In the Free case, pattern-match the underlying pair out if each of the instruction-set 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.
Assume that two implementation functions 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 pre-defined 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 side-effects if I know that the code is pure. With a free monad, I do have to worry about side-effects, because, although the ASTs are pure, an impure interpreter will cause side-effects to happen. At least, however, the side-effects 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:

Decision flowchart for whether or not to choose free monads as a design principle.

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 long-running, impure interactions, then consider whether purity, or strictly functional design, is important to you. F# is a multi-paradigmatic language, and it's perfectly possible to write code that's impure, yet still well-structured. 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 long-running, 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 problem-solving, 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 command-line 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 command-line 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 pattern-match. 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 object-oriented interface. If this is true, then object-oriented interfaces and AST-based free monads are isomorphic.



Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or Google Plus, or somewhere else with a permalink. Ping me with the link, and I may add it as a comment.

Published

Monday, 07 August 2017 08:11:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!