Free Monad
Free monads build on many of the previous concepts in this section and add some nice features. There are many scholarly papers on this topic. I found Runar's presentation from ScalaDays 2014 in Berlin especially helpful. Like with Monads, a cottage industry has cropped around describing Free Monads. To learn more, we point you to the web to find deeper descriptions. We have included a brief description.
Free Monads are often covered in the context of "interpreted languages" so we will use that thought in the next few paragraphs.
If you develop a "language" in your program you need to create an interpreter that interprets that language.
There are many different types of "interpreters" you can embed into a JVM-based language. For example, there is a scripting API where you can embed javascript or the language of your choice into a jvm-based program. The scripting language typically provides a general purpose "context" that stores computation results. The syntax is based on the scripting engine of choice.
Another way to create an interpreted language without using a scripting engine is to create an Abstract Syntax Tree (AST) using the type system in your language. Then an interpreter interprets the AST. In the typical approach, you need some type of "context" that stores intermediate computations. Other approaches may be more clever.
A variation of the AST approach is to create an instruction stream. Instead of retaining an AST per se, you directly compose an instruction stream that is executed by the "interpreter." In most implementations, a "context" is still needed to store intermediate computation. If you have a list of instructions, you need to walk over the list to execute them--you need to fold over them. If each instruction is itself a Functor, then you need to fold and map at the same time. In the Free Monad literature this is called foldMap. foldMap is fairly general and can be applied to a list of instructions or an AST to run the instructions.
A Free Monad is a design pattern for creating interpreted languages but there are other uses as well.
For example, consider the following for-comprehension:
In a for-comprehension, a single Monad type needs to be used for each line (that is, each flatMap/map desugared level). In the example above, the Monad is Option[Int]. All of your functions need to be lifted or projected to return on Option. This can be inconvenient and awkward to maneuver all of your return values to the same monad. Each function call on each line of the for-comprehension could return a different Monad. You could use a Monad transformer to transform one Monad into another but transformers become awkward quickly. Another approach is to use a Free Monad.
If you use a Free Monad, each line of a for-comprehension can have a different Monad and each of those Monad types are lifted into a Free monad, and hence, a common Monad is actually used in the for-comprehension. Each instruction, each line of the for-comprehension, can have a different monadic return type. It's much like the concept of "one more level of indirection" can solve many problems.
A Free monad is a monad whose flatMap does not impose any constraints on the Monad you can return. Instead of being constrained by a rigid flatMap definition, you are "free" to choose the monad to flatMap into.
This is why Runar mentions in his talk that Free Monad's subsumes dependency injection because you can setup your dependencies in the for-comprehension and use them directly in the yield part to perform a computation. All of the dependencies are available using the variable assignment in the for-comprehension.
A Free Monad is a Monad derived from a Functor with the ability to specify the flatMap without "constraints." Category theory has a precise definition of a Free Monad that we will not use here.
A Free Monad can be directly derived from a Functor without you the programmer having to specify the flatMap rigidly e.g. you do not have to force the return value to be the same monad because you can cast the the entire monad into the same Monad. But like anything that sounds "free", an assumption has to be made, somewhere, that allows you to turn a Functor into a Free Monad. In other words, you do not fixate on the flatMap, you fixate on the Monad itself.
A regular Monad is already a Functor so you can turn a regular Monad into a Free Monad. The original Monad's flatMap becomes "overridden." A Free Monad that was created from a Monad often renders the new Monad a "forgetful Monad" because the existing flatMap is not fully used. A Free Monad is itself a Monad. Because it can take a regular Monad and transform it into another Monad, a Free Monad is also a Monad transformer.
The core assumption made that allows you to turn a Functor into a Free Monad with great flexibility into what the flatMap does is quite simple. We should motivate it with an example first using the "instruction stream" idea discussed earlier.
Assume that you wanted to create an instruction stream. Each instruction has a type, say I. To create a set of instructions, you could easily use tuples to create a "list."
But this formulate is a very difficult to work with because each instruction stream would be a different type. If you add another instruction to the "list" you are creating another type. It is impractical to have a different type for each instruction stream. You will also have to create a new interpreter to interpret the instruction stream that matches the instruction stream type--an exhausting thought to contemplate.
First, lets assume that each instruction in the list is a Free Monad. Why make this assumption? A Free Monad, just like a Monad, is like a context with a value inside. That value could be a value like an Int or it could be another instruction. When each instruction a Free Monad, the instructions can express greater computation complexity while still being reasonably easy to manipulate in a program. Since each instruction is a Free Monad, we must also wrap the value a represented by type A. Since each instruction is chained to the instructions that come after it, we need a way to chain the next instruction. We know that flatMap sequences operations. We need some way to group together the current instruction together with the next instruction. flatMap is known as bind so we can use Runar's notation:
Pure allows us to lift a value into the Free Monad. Bind enables us to chain together the current instruction with the next instruction. Instead of directly specifying the next instruction, a function should be provided that returns the next instruction given the current instruction. This allows the instruction stream to branch or perform other sequencing logic. Given the definition above you can also see that you are limiting next to either a Return or more instructions via Bind. F[_] is your instruction set that you create.
The two subtraits have essentially the same type signature as the methods on a Monad:
By comparing these two code blocks, we can see that we are building a Monad by recursively iterating on the Monad itself through the f parameter in flatMap. As a programmer creates the flatMaps in textual programming code, you are adding "instructions" to the instruction list. The chained structure returns the next instruction in f as a function so that you can specify the logic that creates the next instruction. You accumulate structure as you type in your flatMaps and you are skipping the "reduction" process (the "join") that would eliminate multiple layers of nested Monad structure. This means you are only using pure and map to create the Monad as flatMap is a combination of map and join. Because the reduction never happens and you only need to specify map. You can also see that if the F[_] is already a Monad, it will ignore that Monad's flatMap/bind and only use the map part. Hence the common term "forgetful Monad."
A Free Monad, because it can transform another Monad or Functor into a Monad, allows us to take any set of "instructions" and turn them into a Free Monad. We can have many different instruction sets but each needs to eventually lift into the Free Monad so they can be composed together.
The Free Monad is wrapping the existing Functor/Monad. In the for-comprehension example earlier, we had the problem where we wanted to use different Monads in the for-comprehension. By transforming an existing Monad into a Free Monad we can then use Free Monad's in each part of the for-comprehension. This is the same thing as specifying an instruction stream. All that is needed is to convert the existing Monads into a Free Monad.
To convert a set of Monad's into a Free Monad, you need to create a Coproduct. In the Coproduct section, we mentioned that an example of a Coproduct is Either. Either can be either type A or type B. Generalizing this, if you have several Monad types that need to be converted to a single type so that it can be transformed into a Free Monad, you need to specify the Coproduct of all the disjoint types in your "instruction" set. If you want to merge an Option, a String and a List as Monad's, you would form a Coproduct of an Option, String and List by "injecting" those values into the Coproduct. Then you would lift the Coproduct into the Free Monad. Your Free Monad can now describe any instruction in your Coproduct.
The Free Monad is a bit complex so the links below can help you find out more about Free Monads. The first one is Runar's presentation.
The Free Monad is used in fs2 to create "instruction streams" for obtaining items from a stream and applying an algorithm to those items. My using a Free Monad, evaluation can be delayed and concurrency/parallelism controlled more explicitly.
Last updated