The Free Monad and its Cost
This is the follow up post in to my explanation of
Monads for Scala developers. Read part one here.
Code examples can be found here: https://github.com/robinske/monad-examples
I had heard a lot of things about the
Free Monad and never really understood what it was, so did the research that led me here. I wanted to grasp the mechanics within the Scala ecosystem and the reasoning behind its use. Again, we start with Monoids…
A quick refresh on
There is such a thing as a Free Monoid. A
Monoid is “free” when it’s defined in the simplest terms possible and when the
append method doesn’t lose any data in its result.
This is vague, but let’s look at some examples:
ListConcat is “free” - we still have the individual elements of each input list after we’ve concatenated them. We didn’t perform any fancier combinations on the elements given other than throwing them together in sequential order (Integer addition, on the other hand, defines a special algebra for combining numbers, losing the inputs in the result).
It’s also important that we defined
ListConcat with a generic type
A - the only operations we can perform on the generic list are the
Monoid operations (since you don’t know anything about its members, if they’re Strings, Ints, other complex types, or even functions). This satisfies the “simplest terms possible” clause for free-ness, and gives meaning to this technical explanation of Free Objects:
Informally, a free object over a set
Acan be thought of as being a “generic” algebraic structure over
A: the only equations that hold between elements of the free object are those that follow from the defining axioms of the algebraic structure. 1
So why do we call it “Free”?
The word “free” is used in the sense of “unrestricted” rather than “zero-cost” 2
As we saw in the concatenation example above, the
append operation just shoves the data together, “free” of interpretation of the contained data.
But still - why that specific word, “free”? …[It] is free from any specific interpretation, or free to be interpreted in any way. 3
The Free Monad
Let’s think now about what would make a
Monad “free”. We know we want the simplest definition possible, free from interpretation, without losing data.
append definition we used for
Monad in the last post won’t work, since we lose information about the input functions and essentially create some special return function. Instead, we’re have to concatenate or chain the functions in a list-like structure to preserve the data.
We can illustrate this by building the following types: 4
We need these classes (
FlatMap) to capture and store the functions as we chain our Free Monads together. Remember, if we want to stay “free” we can’t evaluate any of the functions as we’re doing this.
Let’s build out an example. Here we have a Free Monad for actions on a Todo list:
You might start to see how we can now encode computations as data and chain the operations together in something like:
Neat! Now you can chain your functions together using a for-comprehension. Keep in mind that nothing has happened yet. We’re “lifting” our actions into the free structures, building up a data structure to be evaluated later. Let’s look at the resulting data structure:
Now you can see the “list-like” data structure that is preserving the functions as we chain them together.
We’ve entered the
Monad, but how do we leave? All of this “free from interpretation” has to come due at some point, and that point is in defining the interpreter(s). These interpreters will evaluate the monad, possibly with side effects, producing the result.
We can define our run function as follows:
We use the
FunctorTransformer to take our input context and transform it into its result. This is what enables us to have a generic run function and define multiple interpretations.
You might also hear this called a
natural transformation or see it defined using this symbolic operator:
~>. In the interest of being explicit I called it a functor transformer.
It’s important that the transformed functor,
G, is also a
Monad so we can use it to flatMap. That’s because we want to stop execution in the chain if our transformation “fails”.
Here’s an example of a test interpreter we can define for our Todo list:
And now we can run this and test against a list of expected actions:
Play around with the code and build your own interpreters using by forking this repo.
Monads vs. Free Monads
What’s the point of using the
Monads have the ability to
flatMap, so we could compose functions for days to achieve a similar end result.
1) Stack safety
Imagine, though, a nested flatMap:
Over the course of your programs you’ll build up something similar - you have composed a bunch of functions that are each added to the stack. If your business logic is complicated enough (in this case, maybe the
doSomething functions are recursive or making
n additional function calls), you might encounter
Free Monad, on the other hand, created a nested, list-like structure that stores all of the functions on the heap. The trick is that these then have to be evaluated in a loop (or a tail recursive call).
The tradeoff? Stack for Heap.
2) Multiple interpreters
Because we’re chaining the data together without any interpretation, we can later define multiple interpreters to handle our Free Monad. This could be something like a test and production interpreter.
3) Defer side effects
We’re deferring execution and interpretation by defining the DSL (domain specific language) to represent our data (the Todo list classes). We don’t do anything with that until we define and run the interpreters, which means that handling of side effects is deferred until the interpretation stage at the very end.
With Great Power…
Free Monads are a powerful construct, but even with their benefits, we should be judicious in our use of these tools. I get nervous every time I find a “neat” solution in Scala, it usually means there is an easier way. We already have a whole slew of tools (builtin to the language) that give the benefits of
Monads (composability, side effect management) without the complexity that require blog posts like these to explain. Remember that the wrong abstraction is dangerous and our responsibility as programmers should still be to write reuseable, maintainable code. In short, more #blueskyscala!
If you’re interested in learning more I talked about this at Scala Days in May, you can watch the video below!
Slides from my Scala Days talk:
Notes and references: