The Free Monad and its Cost

Engineering Team Lead, Optimization

Does this sound interesting?

We're Hiring

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…

Free Monoids

A quick refresh on Monoids:

1
2
3
4
5
6
7

trait Monoid[A] {

  def append(a: A, b: A): A

  def identity: A

}

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:

1
2
3
4
5
6
7

class ListConcat[A] extends Monoid[List[A]] {

  def append(a: List[A], b: List[A]): List[A] = a ++ b

  def identity: List[A] = List.empty[A]

}

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 A can 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.

The 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

sealed trait Free[F[_], A] { self =>

  def flatMap[B](fn: A => Free[F, B]): Free[F, B] =
    FlatMap(self, (a: A) => fn(a))

  def pure[T](a: T): Free[F, T] = Return(a)

  def map[B](fn: A => B): Free[F, B] =
    flatMap(a => pure(fn(a)))

}

case class Return[F[_], A](given: A) extends Free[F, A]

case class Suspend[F[_], A](fn: F[A]) extends Free[F, A]

case class FlatMap[F[_], A, B](free: Free[F, A], fn: A => Free[F, B]) extends Free[F, B]

We need these classes (Return, Suspend, and 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:

1
2
3
4
5
6
7
8
9
10
11

sealed trait Todo[A]
case class NewTask[A](task: A) extends Todo[A]
case class CompleteTask[A](task: A) extends Todo[A]
case class GetTasks[A](default: A) extends Todo[A]

def newTask[A](task: A): Free[Todo, A] = Suspend(NewTask(task))

def completeTask[A](task: A): Free[Todo, A] = Suspend(CompleteTask(task))

def getTasks[A](default: A): Free[Todo, A] = Suspend(GetTasks(default))

You might start to see how we can now encode computations as data and chain the operations together in something like:

1
2
3
4
5
6
7
8

val todos: Free[Todo, Map[String, Boolean]] =
  for {
    _     <- newTask("Go to scala days")
    _     <- newTask("Write a novel")
    _     <- newTask("Meet Tina Fey")
    _     <- completeTask("Go to scala days")
    tasks <- getTasks(default = Map.empty[String, Boolean])
  } yield tsks

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

val todosExpanded: Free[Todo, Map[String, Boolean]] =
  FlatMap(
    Suspend(NewTask("Go to scala days")), (a: String) =>
    FlatMap(
      Suspend(NewTask("Write a novel")), (b: String) =>
      FlatMap(
        Suspend(NewTask("Meet Tina Fey")), (c: String) =>
        FlatMap(
          Suspend(CompleteTask("Go to scala days")), (d: String) =>
          Suspend(GetTasks(default = Map.empty))
        )
      )
    )
  )

Now you can see the “list-like” data structure that is preserving the functions as we chain them together.

Hotel California

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def runFree[F[_], G[_]: Monad, A](f: Free[F, A])(transform: FunctorTransformer[F, G]): G[A] = {
  @annotation.tailrec
  def tailThis(free: Free[F, A]): Free[F, A] = free match {
    case FlatMap(FlatMap(fr, fn1), fn2) => tailThis(fr.flatMap(a1 => fn1(a1).flatMap(a2 => fn2(a2))))
    case FlatMap(Return(a), fn)         => tailThis(fn(a))
    case _                              => free
  }

  val G = Monad[G] // uses implicit objects in constructor

  tailThis(f) match {
    case Return(a)                => G.pure(a)
    case Suspend(fa)              => transform(fa)
    case FlatMap(Suspend(fa), fn) => G.flatMap(transform(fa)){ a => runFree(fn(a))(transform) }
    case _                        => throw new AssertionError("Unreachable")
  }
}

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.

1
2
3

trait FunctorTransformer[F[_], G[_]] {
  def apply[A](f: F[A]): G[A]
}

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

case object ActionTestInterpreter extends FunctorTransformer[Todo, Id] {
  var actions: List[Todo[String]] = List.empty
  def apply[A](a: Todo[A]): Id[A] = {
    a match {
      case NewTask(task) =>
        actions = actions :+ NewTask(task.toString)
        task
      case CompleteTask(task) =>
        actions = actions :+ CompleteTask(task.toString)
        task
      case GetTasks(default) =>
        actions = actions :+ GetTasks("")
        default
    }
  }
}

And now we can run this and test against a list of expected actions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

describe("Free") {
  it("should evaluate todos with an action evaluator") {
    runFree(todos)(ActionTestEvaluator)

    val expected: List[Todo[String]] =
      List(
        NewTask("Go to scala days"),
        NewTask("Write a novel"),
        NewTask("Meet Tina Fey"),
        CompleteTask("Go to scala days"),
        GetTasks("")
      )

    ActionTestEvaluator.actions shouldBe expected
  }
}

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 Free Monad? 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: 

1
2
3
4
5
6
7
8
9

(1 to 1000).toList.flatMap { i =>
  doSomething(i).flatMap { j =>
    doSomethingElse(j).flatMap { k =>
      doAnotherThing(k).map { l =>
        println(l)
      }
    }
  }
}

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 StackOverflowErrors.

The 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:

  1. https://en.wikipedia.org/wiki/Free_object ↩

  2. https://hackage.haskell.org/package/free ↩

  3. https://softwaremill.com/free-monads/ ↩

  4. https://github.com/robinske/monad-examples/blob/master/src/main/scala/me/krobinson/Free.scala ↩