Free Monads, Part One

This post is the first of a series; the next article will cover constructing an application using the CoProduct of Free monads (essentially putting the lego blocks together)

When I was growing up, my grandmother used to tell me “There’s nothing new under the sun […]”. As a child, this seemed like an odd thing to say: clearly new things were invented all the time, so this couldn’t be right, could it?… Of course, as we get older, one realises that indeed many “new” things are just the same thing repacked, polished or slightly altered but they are fundamentally the same thing, and my grandmother was indeed correct: rare is the occasion there’s anything truly new to the world. This experience is one i’m sure is shared by many people as they grow up, and i’d like to draw an interesting parallel here with Functional Programming (FP): and over the past years I have repeatedly had these eureka moments; realising that something I was solving had indeed already solved many moons before by someone else - one simply had not made the connection between the abstraction and the problem. Today was one of these days.

Like many engineers, I am gainfully employed to build large systems that feature an abundant array of non-trivial business logic, and which subsequently have many moving parts to deliver the end solution. The complexity aspect of these moving parts has always bothered me, and over time I had sought out a range of different abstractions to try and alleviate the building of such applications. However, all these solutions pretty much suck, or have some aspect of jankyness, and testing can frequently be a problem, as despite best effort, things can often become awkwardly coupled as a codebase evolves and requirements shift under you.

With this frame, recently I have been investigating Free monads, and my-my, what a delightfully powerful generic abstraction these things are! In this post I will be covering how to implement the much-loved task of logging in terms of scalaz.Free.

Domain Algebra

Before we dive into any specifics about Free, we should first consider the operations necessary for the domain you want to implement, a.k.a the domain algebra. In the case of logging, the domain is of course very small, but it should be familiar to many folks:

// needs to be covarient because of scalaz.Free 7.0.4; 
// in the 7.1 series its no longer covariant - thanks Lars!
sealed trait LogF[+A] 
object Logging {
  case class Debug[A](msg: String, o: A) extends LogF[A]
  case class Info[A](msg: String, o: A) extends LogF[A]
  case class Warn[A](msg: String, o: A) extends LogF[A]
  case class Error[A](msg: String, o: A) extends LogF[A]
}

As you can see, our “domain” simply involves the different levels of log messages, DEBUG through ERROR. The purpose here is to model every single operation in that domain as an ADT. This essentially the command concept in CQRS, which is just another name for algebra (I use this analogy as perhaps more people are familiar with CQRS). Let’s look at the details a little more closely:

sealed trait LogF[+A] 

The LogF trait in this example really does nothing at all; it just serves as the “top level” marker, which we shortly provide a Functor for (hence being called, LogF)

case class Debug[A](msg: String, o: A) extends LogF[A]

The algebra itself needs to extend LogF and take all the arguments required to execute that domain operation (in this case, a single String to print to the output, but you can imagine having a higher number of parameters to actually do something more useful). As for the o: A, this is a vehicle to make the Free abstraction work - in essence, it is the “next computation step”, and we can wire that in by virtue of LogF having a Functor, like so:

implicit def logFFunctor[B]: Functor[LogF] = new Functor[LogF]{
  def map[A,B](fa: LogF[A])(f: A => B): LogF[B] = 
    fa match {
      case Debug(msg,a) => Debug(msg,f(a))
      case Info(msg,a)  => Info(msg,f(a))
      case Warn(msg,a)  => Warn(msg,f(a))
      case Error(msg,a) => Error(msg,f(a))
    }
}

As you can see, all this Functor instance does is take the incoming ADT and apply the function f to the A argument, which allows us to thread the computation through the ADT in a very general fashion.

So this is our domain algebra - right now this is nothing more than a definition of possible operations; it is totally inert, so we need some way to interpret the possible operations, and actually do something about them; this brings us neatly onto interpreters.

Interpreters

In the domain of logging, the content to be logged is totally disjoint from what is done with that content, for example, perhaps we want to use SLF4J in production, but println whilst we’re developing, or perhaps we just want the flexibility to decide later how we should actually do the logging. When designing your system in terms of domain algebra and Free, this becomes trivial, as you simply need to provide a different interpreter implementation that uses whatever implementation you fancy. Let’s look at an implementation that uses println:

object Println {
  import Logging._
  import scalaz.{~>,Id}, Id.Id

  private def write(prefix: String, msg: String): Unit = 
    println(s"[$prefix] $msg")

  private def debug(msg: String): Unit = write("DEBUG", msg)
  private def info(msg: String): Unit  = write("INFO", msg)
  private def warn(msg: String): Unit  = write("WARN", msg)
  private def error(msg: String): Unit = write("ERROR", msg)

  private val exe: LogF ~> Id = new (LogF ~> Id) {
    def apply[B](l: LogF[B]): B = l match { 
      case Debug(msg,a) => { debug(msg); a } 
      case Info(msg,a) => { info(msg); a } 
      case Warn(msg,a) => { warn(msg); a } 
      case Error(msg,a) => { error(msg); a } 
    }
  }

  def apply[A](log: Log[A]): A = 
    log.runM(exe.apply[Log[A]])
}

For the most part, this should be really straightforward to read as all its doing is providing some small part of code that actually does the work of printing to the console. The part that that is of interest is the def apply[A](log: Log[A]): A method, as this is where the awesome is taking place. Notice that the argument is of type Log[A]. Until now, we have not defined this, so let’s add a definition and explain it:

type Log[A] = Free[LogF, A]

So Log is just a type-alias for a Free monad on the LogF functor we defined earlier. This sounds a lot worse than it is; but in essence it just means that Log[A] is actually any constructor of Free, of which there are two options:

• Suspend - the intuition here is “stop the computation and hand control to the caller”.
• Return - and similarly, “i’m done with my computation, here’s the resulting value”

So, with this in mind, assuming there is a Log[A] passed in, Free defines the method runM which will recursively execute the free until reaching the Return (essentially flatMap that shit all the way down, so to speak). In order for this to happen, the caller needs to supply a function S[Free[S, A]] => M[Free[S, A]], or more specifically in terms of this example: LogF[Free[LogF, A]] => Id[Free[LogF, A]], and this is exactly the purpose of the exe value - it takes the domain algebra and executes the appropriate function in the interpreter and “threads” the A through the computation, simply by returning it in this case (as the logging is a side-effect).

Now you have the algebra for the domain, and a way to interpret that, let’s add some syntax sugar so that this stuff is conveniently usable in an application.

MOAR SUGUAARRR

It would be nice if the API would look something like:

object Main {
  import Logging.log

  val program: Free[LogF, Unit] = 
    for {
      a <- log.info("fooo")
      b <- log.error("OH NOES")
    } yield b

  def main(args: Array[String]): Unit = {
    Println(program)
  }
}

Well it turns out that we can conveniently achieve this by lifting the LogF instance into Free, by virtue of the LogF being a Functor… sweet!

implicit def logFToFree[A](logf: LogF[A]): Free[LogF,A] = 
  Suspend[LogF, A](Functor[LogF].map(logf)(a => Return[LogF, A](a))) 

Then we can simply define some convenient usage methods and make the A that we are threading through a Unit, as the act of printing to the console has no usable result.

object log {
  def debug(msg: String): Free[LogF, Unit] = Debug(msg, ())
  def info(msg: String): Free[LogF, Unit]  = Info(msg, ())
  def warn(msg: String): Free[LogF, Unit]  = Warn(msg, ())
  def error(msg: String): Free[LogF, Unit] = Error(msg, ())
}

Critically, using Unit here is simply a product of having no usable value - if we wanted to make a “logger” that was entirely pure and only dumped its output to the console at the end of the application, we could simply write an interpreter that accumulated the content to log in a List[String]!

With the sugar defined, an algebra and an interpreter, all that’s left is to run execute the main :-)

> run

You will then see the output in the console as executed by the println calls.

Replacing the Interpreter

Let’s say that we later decided that using println did not provide sufficient control, and instead we wanted to use SLF4J, then one could easily implement another interpreter that sent the content to that different backend. Here’s an example:

object SLF4J {
  import Logging._
  import org.slf4j.{Logger,LoggerFactory}

  private val log = LoggerFactory.getLogger(SLF4J.getClass)

  private val exe: LogF ~> Id = new (LogF ~> Id) {
    def apply[B](l: LogF[B]): B = l match { 
      case Debug(msg,a) => { log.debug(msg); a } 
      case Info(msg,a) => { log.info(msg); a } 
      case Warn(msg,a) => { log.warn(msg); a } 
      case Error(msg,a) => { log.error(msg); a } 
    }
  }

  def apply[A](log: Log[A]): A = 
    log.runM(exe.apply[Log[A]])
}

As you can see, the only difference is the SL4J plumbing is encapsulated within the interpreter, but absolutely nothing has changed about how the program will be defined - only how it is actually actioned changes. The actual application main then just becomes:

def main(args: Array[String]): Unit = {
  SLF4J(program)
}

You can find all the code for this post over on Github.