Free Monads in Scala Explained

Writing Programs With The Free Monad

Let’s imagine we’re writing a small tool to interact with a custom database we have at work. For the sake of simplicity, we’ll assume the fundamental operations of the database to be the regular CRUD:

trait DBOps[A]
case class Create[A](key: String, value: A) extends DBOps[Unit]
case class Read[A](key: String) extends DBOps[A]
case class Update[A](key: String, value: A) extends DBOps[A]
case class Delete(key: String) extends DBOps[Unit]

This suite of operations (some of which can wrap others in real libraries) bears the fancy name of “algebra”, for the reason that any expression composed out of these fundamental types through some operators (like nesting or regular methods) belong to this group as well.

It’s easy to imagine an example of an interaction with such a database:

• Read something from a key, like the name of a person
• Change it, e.g. run a toUppercase on it
• Associate this new value to another key
• Delete the old key

This is a sequential suite of operations. Because it’s sequential, a monadic data type to describe all of these operations can prove very useful. However, instead of writing a type class instance for Monad[DBOps] and following the tagless-final approach, we’re going to use a Free monad:

type DBMonad[A] = Free[DBOps, A]

Because we’re using a Free monad, instead of describing combinators of the data types above, we’re going to “lift” them to Free through smart constructors:

def create[A](key: String, value: A): DBMonad[Unit] =
  Free.liftM[DBOps, Unit](Create(key, value))

def get[A](key: String): DBMonad[A] =
  Free.liftM[DBOps, A](Read[A](key))

def update[A](key: String, value: A): DBMonad[A] =
  Free.liftM[DBOps, A](Update[A](key, value))

def delete(key: String): DBMonad[Unit] =
  Free.liftM(Delete(key))

and with these smart constructors in place, we can immediately imagine an abstract program that does what we said above — read, change, create new entry, delete old entry:

  def myLittleProgram: DBMonad[Unit] = for {
    _ <- create[String]("123-456", "Daniel")
    name <- get[String]("123-456")
    _ <- create[String]("567", name.toUpperCase())
    _ <- delete("123-456")
  } yield ()

This program can be completely described in terms of the Free monad, regardless of what wrapper type we use. The only problem is that it’s a description of a computation; it does not perform any meaningful work in the world, like, you know, interacting with an actual database.

We need something to interpret this program.

Free Monad FoldMap

What does “interpretation” even mean? Interpreting a program means transforming this abstract program written in terms of the Free monad into another data type that actually performs the computations when evaluated. A good candidate for such a data structure is, for example, the Cats Effect IO. However, we can pick another data type of our choosing, with the meaning of

• Potentially absent values: Option
• Potentially failed computations: Try
• Potentially failed computations with an error type of our choosing: Either
• Computations that can perform side effects: IO
• Combinations of the above: ZIO
• Aggregating values: List

This is why the Free monad has another operation that can “evaluate” an instance of Free to one of these data types. The operation is called foldMap and looks like this:

trait Free[M[_], A] {
    // ... existing code
    def foldMap[G[_]: Monad](natTrans: M ~> G): G[A]
}

This one is a bit more complicated. Let’s take each piece in turn.

First of all, what’s a natTrans and the ~> symbol? The concept of “natural transformation” is a higher-kinded Function1 type that looks like this:

  trait ~>[F[_], G[_]] {
    def apply[A](fa: F[A]): G[A]
  }

So instead of a regular Function1 taking value types as type parameters, now we operate at a higher kind. We used this concept in our demonstration for why monads are monoids in the category of endofunctors. Examples of natural transformations in real life include:

• Try[A].toOption: this is an example of an implementation of a natural transformation between Try and Option
• List[A].headOption which returns the head of the list, if it exists: an example of an implementation of a natural transformation between List and Option
• Option[A].toList: the reverse

We can abstract away this concept of natural transformation by the ~> symbol, which looks like a function type at a higher kind.

Back to foldMap. Notice that the return value of foldMap is G[A], so a different monadic type than M[_], assuming that G “is” a Monad, by the context bound G[_]: Monad. This is important, because the evaluation of an instance of Free can only happen if the wrapper type which we’re evaluating to is also a monad, i.e. exhibits monadic behavior.

Natural Transformations

For our little program, we can interpret it with foldMap, if we can create a natural transformation from our type DBOps to some other type that will actually perform the actions described by the program. Let’s write a simple IO data type in the style of Cats Effect:

case class IO[A](unsafeRun: () => A)
object IO {
  def create[A](a: => A): IO[A] = IO(() => a)
}

The IO type encapsulates computations that evaluate to A, with potential side effects. The IO data type is a monad, meaning that we can create a Monad instance for it:

given ioMonad: Monad[IO] with {
  override def pure[A](a: A) =
    IO(() => a)
  override def flatMap[A, B](ma: IO[A])(f: A => IO[B]) =
    IO(() => f(ma.unsafeRun()).unsafeRun())
}

Being a monad, the IO data type is a suitable “evaluator” for our abstract program. The only piece that we need is a natural transformation from DBOps to IO. This natural transformation is the logic of evaluating the abstract CRUD operations (for now just data structures) into actual effects in the real world. For that, we’ll need an actual database to store and retrieve data. For this simple example, we’ll assume a simple mutable map, but this can easily be replaced in practice by a real database.

val myDB: mutable.Map[String, String] = mutable.Map()

For our particular database, in order to read/write values of type A, we’ll also provide some awesome serialization/deserialization API to/from String:

def serialize[A](a: A): String = a.toString
def deserialize[A](value: String): A = value.asInstanceOf[A]

Of course, with your own database, the communication protocol will be different, but for this example it’ll be sufficient.

The natural transformation from DBOps to our IO data type will need to take the “database” and the “protocol” into account. All we need to do is convert all cases of DBOps into proper IOs that will perform effects on the database when evaluated, so we can resort to simple pattern matching for this:

val dbOps2IO: DBOps ~> IO = new (DBOps ~> IO) {
  override def apply[A](fa: DBOps[A]): IO[A] = fa match {
    case Create(key, value) => IO.create {
      // database insert query - here, just printing
      println(s"insert into people(id, name) values ($key, $value)")
      myDB += (key -> serialize(value))
      ()
    }
    case Read(key) => IO.create {
      println(s"select * from people where id=$key limit 1")
      deserialize(myDB(key))
    }
    case Update(key, value) => IO.create {
      println(s"update people(name=$value) where id=$key")
      val oldValue = myDB(key)
      myDB += (key -> serialize(value))
      deserialize(oldValue)
    }
    case Delete(key) => IO.create {
      println(s"delete from people where id=$key")
      ()
    }
  }
}

Evaluating the Program

With all pieces in place, we can now run the interpreter of our abstract program with foldMap and with the natural transformation we’ve just implemented:

val ioProgram: IO[Unit] = myLittleProgram.foldMap(dbOps2IO)

This is a single IO[Unit] effect which can be passed around, reused, or “run” in main:

def main(args: Array[String]): Unit = {
  ioProgram.unsafeRun() // PERFORMS THE ACTUAL WORK
}

This will execute the IO effect, which in turn will evaluate our abstract program.

The Free Monad Pattern

Why have we gone all this way just to insert a bunch of data into a database?

The Free monad is a pattern which allows us to separate

• The description of fundamental operations
• The business logic of our application
• The evaluation of that business logic

In other words, our abstract program is what matters for our application/business logic. We can keep that fixed, and give it different interpreters depending on how our requirements change — e.g. perhaps we want the program to be evaluated asynchronously — or we can do the reverse. This makes it very easy to maintain, because we can work independently on either

• The business logic, while keeping interpreters fixed
• The interpreters, while keeping the business logic fixed
• The fundamental operations and the interpreter(s), while keeping the business logic fixed

So notice the flexibility we get by choosing to work on a piece of the system without affecting the others. Another benefit of this approach is testability, because we can always supply a “testing” monad to evaluate the program, make assertions and ensure the business logic is correct, while the interpreter itself can be independently tested.

Final Code

The full program with all pieces put together looks like this:

object FreeMonad {
  trait Monad[M[_]] {
    def pure[A](a: A): M[A]
    def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
  }

  object Monad {
    def apply[M[_]](using monad: Monad[M]): Monad[M] = monad
  }

  trait ~>[F[_], G[_]] {
    def apply[A](fa: F[A]): G[A]
  }

  trait Free[M[_], A] {
    import Free.*
    def flatMap[B](f: A => Free[M, B]): Free[M, B] = FlatMap(this, f)
    def map[B](f: A => B): Free[M, B] = flatMap(a => pure(f(a)))
    def foldMap[G[_]: Monad](natTrans: M ~> G): G[A] = this match {
      case Pure(a) => Monad[G].pure(a)
      case Suspend(ma) => natTrans.apply(ma)
      case FlatMap(fa, f) => // need a G[B]
        Monad[G].flatMap(fa.foldMap(natTrans))(a =>     f(a)      .foldMap(natTrans) )
    }
  }

  object Free {
    def pure[M[_], A](a: A): Free[M, A] = Pure(a)
    def liftM[M[_], A](ma: M[A]): Free[M, A] = Suspend(ma)

    case class Pure[M[_], A](a: A) extends Free[M, A]
    case class FlatMap[M[_],A,B](fa: Free[M, A], f: A => Free[M, B]) extends Free[M, B]
    case class Suspend[M[_], A](ma: M[A]) extends Free[M, A]
  }

  // sequence computations as data structures, THEN attach the monadic type at the end
  // "algebra"
  trait DBOps[A]
  case class Create[A](key: String, value: A) extends DBOps[Unit]
  case class Read[A](key: String) extends DBOps[A]
  case class Update[A](key: String, value: A) extends DBOps[A]
  case class Delete(key: String) extends DBOps[Unit]

  // definitions - fancier algebra
  type DBMonad[A] = Free[DBOps, A]

  // "smart" constructors
  def create[A](key: String, value: A): DBMonad[Unit] =
    Free.liftM[DBOps, Unit](Create(key, value))

  def get[A](key: String): DBMonad[A] =
    Free.liftM[DBOps, A](Read[A](key))

  def update[A](key: String, value: A): DBMonad[A] =
    Free.liftM[DBOps, A](Update[A](key, value))

  def delete(key: String): DBMonad[Unit] =
    Free.liftM(Delete(key))

  // business logic is FIXED
  def myLittleProgram: DBMonad[Unit] = for { // monadic
    _ <- create[String]("123-456", "Daniel")
    name <- get[String]("123-456")
    _ <- create[String]("567", name.toUpperCase())
    _ <- delete("123-456")
  } yield () // description of a computation

  // evaluate the program - interpreter/"compiler"
  // IO
  case class IO[A](unsafeRun: () => A)
  object IO {
    def create[A](a: => A): IO[A] = IO(() => a)
  }

  given ioMonad: Monad[IO] with {
    override def pure[A](a: A) = IO(() => a)
    override def flatMap[A, B](ma: IO[A])(f: A => IO[B]) =
      IO(() => f(ma.unsafeRun()).unsafeRun())
  }

  val myDB: mutable.Map[String, String] = mutable.Map()
  // TODO replace these with some real serialization
  def serialize[A](a: A): String = a.toString
  def deserialize[A](value: String): A = value.asInstanceOf[A]

  // nat trans DBOps -> IO
  val dbOps2IO: DBOps ~> IO = new (DBOps ~> IO) {
    override def apply[A](fa: DBOps[A]): IO[A] = fa match {
      case Create(key, value) => IO.create { // actual code that uses the database
        println(s"insert into people(id, name) values ($key, $value)")
        myDB += (key -> serialize(value))
        ()
      }
      case Read(key) => IO.create {
        println(s"select * from people where id=$key limit 1")
        deserialize(myDB(key))
      }
      case Update(key, value) => IO.create {
        println(s"update people(name=$value) where id=$key")
        val oldValue = myDB(key)
        myDB += (key -> serialize(value))
        deserialize(oldValue)
      }
      case Delete(key) => IO.create {
        println(s"delete from people where id=$key")
        ()
      }
    }
  }

  val ioProgram: IO[Unit] = myLittleProgram.foldMap(dbOps2IO)

  def main(args: Array[String]): Unit = {
    ioProgram.unsafeRun() // PERFORMS THE ACTUAL WORK
  }
}