The Free Monad — A Versatile Tool for Creating Test Doubles

As we know from the vast literature on software testing, many practical approaches exist for substituting as yet not fully functional software components with so-called test doubles — including stubs, fakes, and mocks. This article will look at a functional programming structure called the Free Monad and consider how it offers an elegant way to create test doubles.

A quick recap of where we are

Before we begin, recall that in these two previous articles, we went through several functional programming concepts, namely functors, monads, contravariant functors, and contravariant monads. Based on some rudimentary examples, we saw how these concepts could be used to write more readable and elegant code in managing dependencies and side effects.

How did we achieve this? Basically, by using the following concepts to:

• Encapsulate the glue between functions: we encapsulated the wrapping and unwrapping of data structures and the passing on of data from one function to the next using canonical functions such as map() and flatmap(). This, in turn, helped us remove a lot of boilerplate code having to do with creating and managing variables and focus solely on the sequence of functions to be called.
• Perform lazy (deferred) evaluation: we stored our functions, or composed chains thereof, as data wrapped in a container such as a (contravariant) functor or a monad. This allowed us to define a series of transformations on both the input to and the output from our function(s) prior to actually running them. As we saw, this allowed us to achieve goals like transforming inputs to our functions or injecting dependencies into them without having to manage explicit state.

Today, we will go one step further and introduce a special type of monad called the free monad. The wonder of free monads is that they can be used to model any sequence of operations so that not only the execution of those operations but also their interpretation can be deferred to a later time. The main idea is to represent each function in our chain of operations as data and wrap each intermediate result into a structure that halts the chain of computations until it is explicitly resumed. This, in turn, will allow all intermediate results to be interpreted as something other than the operations they represent at face value.

In treating this topic, I am again indebted to Brian Lonsdorf, whose very elegant (but somewhat condensed) explanations served as a starting point for this article.

The What and the Why of Free Monads

Luckily, we don’t need to go into the details of what a ‘free category’ means in category theory to understand free monads and to benefit from their use.

Briefly stated, a free monad is a composite data type whose instances can either be Suspend or Pure.

The Suspend (also known as Impure) variant of a free monad encapsulates some value and a deferred operation on that value.

The Pure variant of a free monad, in turn, simply holds a value, usually the starting point or final result of some series of transformations.

Being free as they are, free monads hold the potential to represent more than one kind of data processing pattern. As suggested by the trampoline example (see, e.g., the epilogue in this post), we can implement stack-safe recursive behaviors by creating a function that keeps returning (something similar to) a Suspend object, as long as further recursion is necessary; and (something similar to) a Pure object once the recursion terminates.

However, by now, we should be getting accustomed to the idea that in functional programming, functions (operations) can also be treated as data in their own right and used as inputs to higher-order transformations. So, in this view, the data inside a Suspend object might also be a reified operation whose semantics can be transformed or even reinterpreted as it is being parsed. In this way, one can create domain-specific languages (DSLs) using free monads and create multiple alternative interpreters to parse them — an approach that can be useful for mocking/testing some behaviors without actually running them with all their potential side effects.

Before going into specific examples, let’s take a look at a possible implementation of free monads in JavaScript:

First, let’s consider Pure. Since in native JavaScript, at least, we don’t have the luxury of algebraic data types, we can implement a type() function to be able to query the variant we are working with at any given time (the prefix of the result symbolizes that both Pure and Suspend are part of the free data type). The canonical functions, map() and flatMap(), operate exactly as one would expect.

In the case of flatMap(), the flatmapped function will take care of wrapping the result into a new free (or whatever) monad, so we don’t need to do this explicitly as in the case of map(). toString() will be useful for printing the Pure object to the console, and run() will be necessary if we want to get back the value x that is stored inside the Pure object.

The case of Suspend is less trivial. Remember, in this case, we are working not only with some data x (whatever that may be) but also with some transformations we already want to carry out on x (represented by f). So, if we wanted to run() the Suspend object, we would have to call f(x). If we wanted to map or flatmap a second function, g, onto the Suspend object, the way to go would be to return a new Suspend object that still encapsulates the same data, along with a new transformation that somehow represents a composition of the original transformation and the second transformation, g. Since we don’t know in advance what kind of functor or monad f(x) will return, we can defer the particulars of these operations by mapping or flatmapping g onto the output of f.

Of course, in both cases, we would have to make sure that f(x) will return a type that has a map(g) or flatmap(g) function, respectively, and that the signature of g, in terms of the input it expects, conforms to either of those functions. Otherwise, the chain of computations would break down. To help guarantee this, for our later examples, let’s create a basic monadic wrapper that can encapsulate any basic value as follows:

Now, if both f and g return values wrapped in an Id type, we can be sure that the flatMap function will always exist, and the computations won’t break down (of course, as we will see, we might have other, better alternatives in specific cases).

Before moving on to some more interesting examples, let’s put all of this to the test:

Great! Everything works fine, but we still haven’t reached the main point, so let’s move on!

Simulating Other Monads Using the Free Monad

Since we mentioned that free monads are canonical, let’s look at an example where we implement another monad using free monads. For this example, we will consider the Maybe monad, which is often used to represent the results of a computation that can either succeed or fail with no result. The benefit is that when operations return Maybe monads are chained, we do not have to worry about checking whether all intermediate computations were successful.

An instance of the Maybe monad can be Just(x) (where x is the result of a successful operation), or Nothing(), which is a primitive representing an unsuccessful computation.

To map the Maybe monad onto the Free monad, so to speak, we first need to lift these two objects into the context of Pure and Suspend. Let’s take a look at how we might do this:

In our application code, we will (mostly) use the capitalized versions of Just and Nothing. These are both functions that either take a value (x in the case of Just) or nothing (in the case of Nothing) and lift them into the context of a Suspend object. This Suspend object promises to wrap a lowercase just(x) or nothing() object, respectively, into a Pure object at some later time (when the Suspend is fully finalized and run).

Leaving out the toString functions, the data itself that represents the just(x) or nothing() objects either has the form {x, type: () => ‘maybe.just’} or {type: () => ‘maybe.nothing’}.

Since a Just(x) or a Nothing() is now really just a Suspend object under the hood, in theory, we can map or flatmap other functions onto them. Since the internally stored function, f, inside the Just(x) or Nothing() is defined to (eventually) return a Pure(just(x)) or a Pure(nothing()), calling flatMap(g) on either Suspend object will return a new Suspend object whose internally stored function, f, will just be a continuation on either of those Pure objects, i.e., Pure(…).flatMap(g), where the three dots represent either the lowercase just(x) or nothing(). By definition, this expression will translate to either g(just(x)) or g(nothing()).

Running our maybe monad

To see what will happen when we call run on such a Maybe monad, let’s consider the following two examples:

In the first case, maybe1 is just a Suspend object that, once run, will return the stored data wrapped inside a Pure (as per the definition of Just(x)).

But something seems amiss in the second case. Recall that we said that flatmapping a function g on a Just(x) object will just run Pure(just(x)).flatMap(g), which is the same as g(just(x)). So, in our case, when calling maybe2.run(), since g is res => Just(res + 1), what we get back is a Just(just(x) + 1). But what does this expression mean?

Well, we said that Just(x) is actually a Suspend object. So, we now have a new Suspend object that promises to (eventually) return Pure(just(x) + 1), or in other words, Pure(just(x)1), since the JavaScript interpreter will just treat both operands of the + operator as strings (oops… we should have written res => Just(res.x + 1) and this would not have happened). But in any case, since we haven’t yet called run on this new Suspend object, our chain of computations will be halted for now!

As we will see later on, this can be quite a useful feature of flatmapped functions (over the free monad) returning 1 object since we can reinterpret the meaning of the data at each step along the way. But right now, we just want to make sure that run() will be called as many times as necessary to obtain a final result, and the values inside the just(x) objects will get unwrapped at each step along the way (so that the ‘+’ or whatever other operator can get handled as necessary). To achieve this, we can use a special runner function designed specifically for the Maybe monad (in this case):

The good news is that, eventually, our loop of constantly getting a new Just(x) (or Nothing()) back will terminate, and the final Suspend, when run, will return a Pure object. So we can rest assured that when we call runMaybe(), the (seemingly) infinite loop inside it will eventually terminate.

Now, let’s take a look at some examples:

Note that in the second case, the fact that the penultimate computation returned a Nothing() was handled seamlessly by our runMaybe() function (even when we wanted to add 1 to the nonexistent result).

Reinterpreting Abstract Syntax Trees Using the Free Monad

As we’ve seen in the previous example, in principle, it’s possible to implement any monad using the free monad by:

• reifying the monad as a set of data structures
• piggybacking the data structures on the data field of a Suspend object
• such that the operation inside the Suspend object promises to wrap the data field into a Pure

We’ve also seen that when doing this, a special runner function is also needed to ensure that the reified data structures are recursively (and in each iteration, suitably!) processed when the operations we are flatmapping return a new Free monad. By necessity (at least without further abstractions, as we will see), this runner function will be unique to the piggybacked monad since the number of parameters and their semantics in the reified monad will vary on a case-by-case basis.

As a variation on this pattern, before running the operations in the Suspend object(s), we could also transform the data in them into something else. This is useful when this data represents operations that can be carried out as opposed to just representing data (as in the Just(x) and Nothing() case), assuming that we want to interpret the semantics of those operations on the fly.

Let’s consider a simple algebraic example with two interpretations: one literal and one that prints the operations as a string.

To do this, we first define the (lowercase) reified operations and their uppercase versions that are lifted into the realm of the free monad:

Here, again, Div(x, y), Add(x, y), and Mul(x, y) are actually just Suspend objects under the hood that contains the objects representing the lowercase variants div, add, and mul, with the deferred operation of wrapping those into a Pure. However, what is different from the example with the Maybe monad is that div, add, and mul now represent operations that can be carried out, as opposed to being plain numbers (as in the case of, e.g., just(4)).

Next, we define our two interpreter functions, whose task it is to transform the data contained within each intermediate Suspend object before their being run. In other words, when we have our first Suspend object — which promises to wrap the reified operation into a Pure object — and then flatmap our next function, g, onto it, instead of computing, e.g., something like:

Pure(div(6, 2)).flatMap(x => Add(x, 2)) = // which is the same as:
Add(div(6, 2), 2)

We want to compute this…

Pure(interpreter(div(6, 2))).flatMap(x => Add(x, 2)) =
// which is the same as:
Add(interpreter(div(6, 2)), 2)

… and repeat this process until we finish. However, it’s important to note that the interpreter function itself should return a data structure that is agreed upon by convention (ideally, the Id() monad) rather than just a plain value. Why? Because, in general, we can have as many interpreter functions as there are stars in the sky, and we need to ensure that the values we obtain can be handled uniformly. Not to mention that using a monad like Id() can be useful in that we can be sure that the map() and flatMap functions will be defined on the result, so we can continue to string together operations at a higher level.

Our two interpreter functions, then, might look like this:

Regardless of which interpreter function we will be working with, we can be sure that when transforming the value inside any given Free monad, we will get an Id() monad with something inside it.

Our application code, in turn, would still look something like this:

Now, how can we adapt our earlier runner function to carry out the transformations while performing the computations printed above? It turns out there is a generic way to do this called foldMap. This function will combine all operations into a single result (fold) while transforming the intermediate results (map).

To ensure that our foldMap function has the same number and type of arguments in both the Pure and Suspend case, foldMap() will accept two arguments in both cases: first, the interpreter function itself, and second, the wrapper type that the interpreter function uses to wrap its result (the latter is necessary because in the case of Pure, we might still want to wrap the result into this monad).

Thus, in the case of Pure, all we have to do is wrap the contents of the Pure object into the wrapper type. In the case of Suspend, our task is a tiny bit less trivial. First, we want to use the interpreter to transform the datum inside the object. Next, we will call the function f on the result to obtain our next Suspend or Pure object in the chain and call foldMap() on that new free monad as well:

Now, we have the following:

An Example of the Free Monad Used for Mocking/Testing Applications

The arithmetics example in the previous section was edifying but not very interesting from a practical perspective. So, let’s imagine we are working on a drone and want to mock various operations on it without actually carrying them out (lest we lose it to an accident before even deploying it!)

So, let’s assume we have some functions to manage our drone, like launchDrone(), sendSamplesDrone(), and selfDestruct(). However, instead of calling them directly, we can reify them as data structures and then lift them into the realm of the Free Monad:

Let’s now create a simple Exec monad (truly just a minimalistic object) so that we can flatMap() subsequent functions onto it after carrying out a side effect like printing something to the console (or writing something to a log file). Let’s also create two possible interpreters with the following code:

Now, depending on which interpreter we used, we could mock the operations or carry them out for real:

Summary

As we’ve seen, Free monads can serve as a versatile tool for assembling chains of operations to be carried out later and for reinterpreting the meaning of each of those operations as they are carried out. This idea can be applied as a simulation (or test double) technique.

The Free Monad — A Versatile Tool for Creating Test Doubles was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.