Free monads 

We said that free monoids are examples of free objects. Similarly, free monads are examples of free objects.

I’m not going to get into the details, monad is a monoid in the category of endofunctors F: C => C, using F × F => F as the binary operator. Similar to the way we could derive A* from A, we can derive the free monad F* for a given endofunctor F.

Here’s how Haskell does it:

data Free f a = Pure a | Free (f (Free f a))

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a >>= f = f a
  Free m >>= f = Free ((>>= f) <$> m)

Wikipedia on Monad:

Unlike List, which stores a list of values, Free stores a list of functors, wrapped around an initial value. Accordingly, the Functor and Monad instances of Free do nothing other than handing a given function down that list with fmap.

Also note that Free is a datatype, but there are different free monads that gets formed for each Functor.

Why free monads matter 

In practice, we can view Free as a clever way of forming Monad out of Functor. This is particularly useful for interpreter pattern, which is explained by Gabriel Gonzalez (@gabrielg439)’s Why free monads matter:

Let’s try to come up with some sort of abstraction that represents the essence of a syntax tree. …

Our toy language will only have three commands:

output b -- prints a "b" to the console
bell     -- rings the computer's bell
done     -- end of execution

So we represent it as a syntax tree where subsequent commands are leaves of prior commands:

data Toy b next =
    Output b next
  | Bell next
  | Done

Here’s Toy translated into Scala as is:

sealed trait Toy[+A, +Next]

object Toy {
  case class Output[A, Next](a: A, next: Next) extends Toy[A, Next]
  case class Bell[Next](next: Next) extends Toy[Nothing, Next]
  case class Done() extends Toy[Nothing, Nothing]
}

Toy.Output('A', Toy.Done())
// res0: Toy.Output[Char, Toy.Done] = Output(a = 'A', next = Done())

Toy.Bell(Toy.Output('A', Toy.Done()))
// res1: Toy.Bell[Toy.Output[Char, Toy.Done]] = Bell(
//   next = Output(a = 'A', next = Done())
// )

CharToy 

In WFMM’s original DSL, Output b next has two type parameters b and next. This allows Output to be generic about the output type. As demonstrated above as Toy, Scala can do this too. But doing so unnecessarily complicates the demonstration of Free because of Scala’s handling of partially applied types. So we’ll first hardcode the datatype to Char as follows:

sealed trait CharToy[+Next]

object CharToy {
  case class CharOutput[Next](a: Char, next: Next) extends CharToy[Next]
  case class CharBell[Next](next: Next) extends CharToy[Next]
  case class CharDone() extends CharToy[Nothing]

  def output[Next](a: Char, next: Next): CharToy[Next] = CharOutput(a, next)
  def bell[Next](next: Next): CharToy[Next] = CharBell(next)
  def done: CharToy[Nothing] = CharDone()
}

{
  import CharToy._
  output('A', done)
}
// res2: CharToy[CharToy[Nothing]] = CharOutput(a = 'A', next = CharDone())

{
  import CharToy._
  bell(output('A', done))
}
// res3: CharToy[CharToy[CharToy[Nothing]]] = CharBell(
//   next = CharOutput(a = 'A', next = CharDone())
// )

I’ve added helper functions lowercase output, bell, and done to unify the types to CharToy.

Fix 

WFMM:

but unfortunately this doesn’t work because every time I want to add a command, it changes the type.

Let’s define Fix:

case class Fix[F[_]](f: F[Fix[F]])

object Fix {
  def fix(toy: CharToy[Fix[CharToy]]) = Fix[CharToy](toy)
}

{
  import Fix._, CharToy._
  fix(output('A', fix(done)))
}
// res4: Fix[CharToy] = Fix(
//   f = CharOutput(a = 'A', next = Fix(f = CharDone()))
// )

{
  import Fix._, CharToy._
  fix(bell(fix(output('A', fix(done)))))
}
// res5: Fix[CharToy] = Fix(
//   f = CharBell(next = Fix(f = CharOutput(a = 'A', next = Fix(f = CharDone()))))
// )

Again, fix is provided so that the type inference works.

FixE 

We are also going to try to implement FixE, which adds an exception to this. Since throw and catch are reserved, I am renaming them to throwy and catchy:

import cats._, cats.data._, cats.syntax.all._

sealed trait FixE[F[_], E]
object FixE {
  case class Fix[F[_], E](f: F[FixE[F, E]]) extends FixE[F, E]
  case class Throwy[F[_], E](e: E) extends FixE[F, E]

  def fix[E](toy: CharToy[FixE[CharToy, E]]): FixE[CharToy, E] =
    Fix[CharToy, E](toy)
  def throwy[F[_], E](e: E): FixE[F, E] = Throwy(e)
  def catchy[F[_]: Functor, E1, E2](ex: => FixE[F, E1])
      (f: E1 => FixE[F, E2]): FixE[F, E2] = ex match {
    case Fix(x)    => Fix[F, E2](Functor[F].map(x) {catchy(_)(f)})
    case Throwy(e) => f(e)
  }
}

We can only use this if Toy b is a functor, so we muddle around until we find something that type-checks (and satisfies the Functor laws).

Let’s define Functor for CharToy:

implicit val charToyFunctor: Functor[CharToy] = new Functor[CharToy] {
  def map[A, B](fa: CharToy[A])(f: A => B): CharToy[B] = fa match {
    case o: CharToy.CharOutput[A] => CharToy.CharOutput(o.a, f(o.next))
    case b: CharToy.CharBell[A]   => CharToy.CharBell(f(b.next))
    case CharToy.CharDone()       => CharToy.CharDone()
  }
}
// charToyFunctor: Functor[CharToy] = repl.MdocSession1@2629300

Here’s a sample usage:

{
  import FixE._, CharToy._
  case class IncompleteException()
  def subroutine = fix[IncompleteException](
    output('A',
      throwy[CharToy, IncompleteException](IncompleteException())))
  def program = catchy[CharToy, IncompleteException, Nothing](subroutine) { _ =>
    fix[Nothing](bell(fix[Nothing](done)))
  }
}

The fact that we need to supply type parameters everywhere is a bit unfortunate.

Free datatype 

WFMM:

our FixE already exists, too, and it’s called the Free monad:

data Free f r = Free (f (Free f r)) | Pure r

As the name suggests, it is automatically a monad (if f is a functor):

instance (Functor f) => Monad (Free f) where
    return = Pure
    (Free x) >>= f = Free (fmap (>>= f) x)
    (Pure r) >>= f = f r

The return was our Throw, and (>>=) was our catch.

The datatype in Cats is called Free:

/**
 * A free operational monad for some functor `S`. Binding is done
 * using the heap instead of the stack, allowing tail-call
 * elimination.
 */
sealed abstract class Free[S[_], A] extends Product with Serializable {

  final def map[B](f: A => B): Free[S, B] =
    flatMap(a => Pure(f(a)))

  /**
   * Bind the given continuation to the result of this computation.
   * All left-associated binds are reassociated to the right.
   */
  final def flatMap[B](f: A => Free[S, B]): Free[S, B] =
    Gosub(this, f)

  ....
}

object Free {
  /**
   * Return from the computation with the given value.
   */
  private final case class Pure[S[_], A](a: A) extends Free[S, A]

  /** Suspend the computation with the given suspension. */
  private final case class Suspend[S[_], A](a: S[A]) extends Free[S, A]

  /** Call a subroutine and continue with the given function. */
  private final case class Gosub[S[_], B, C](c: Free[S, C], f: C => Free[S, B]) extends Free[S, B]

  /**
   * Suspend a value within a functor lifting it to a Free.
   */
  def liftF[F[_], A](value: F[A]): Free[F, A] = Suspend(value)

  /** Suspend the Free with the Applicative */
  def suspend[F[_], A](value: => Free[F, A])(implicit F: Applicative[F]): Free[F, A] =
    liftF(F.pure(())).flatMap(_ => value)

  /** Lift a pure value into Free */
  def pure[S[_], A](a: A): Free[S, A] = Pure(a)

  final class FreeInjectPartiallyApplied[F[_], G[_]] private[free] {
    def apply[A](fa: F[A])(implicit I : Inject[F, G]): Free[G, A] =
      Free.liftF(I.inj(fa))
  }

  def inject[F[_], G[_]]: FreeInjectPartiallyApplied[F, G] = new FreeInjectPartiallyApplied

  ....
}

To use these datatypes in Cats, use Free.liftF:

import cats.free.Free

sealed trait CharToy[+Next]
object CharToy {
  case class CharOutput[Next](a: Char, next: Next) extends CharToy[Next]
  case class CharBell[Next](next: Next) extends CharToy[Next]
  case class CharDone() extends CharToy[Nothing]

  implicit val charToyFunctor: Functor[CharToy] = new Functor[CharToy] {
    def map[A, B](fa: CharToy[A])(f: A => B): CharToy[B] = fa match {
        case o: CharOutput[A] => CharOutput(o.a, f(o.next))
        case b: CharBell[A]   => CharBell(f(b.next))
        case CharDone()       => CharDone()
      }
    }
  def output(a: Char): Free[CharToy, Unit] =
    Free.liftF[CharToy, Unit](CharOutput(a, ()))
  def bell: Free[CharToy, Unit] = Free.liftF[CharToy, Unit](CharBell(()))
  def done: Free[CharToy, Unit] = Free.liftF[CharToy, Unit](CharDone())
  def pure[A](a: A): Free[CharToy, A] = Free.pure[CharToy, A](a)
}

Here’s the command sequence:

import CharToy._

val subroutine = output('A')
// subroutine: Free[CharToy, Unit] = Suspend(
//   a = CharOutput(a = 'A', next = ())
// )

val program = for {
  _ <- subroutine
  _ <- bell
  _ <- done
} yield ()
// program: Free[CharToy, Unit] = FlatMapped(
//   c = Suspend(a = CharOutput(a = 'A', next = ())),
//   f = <function1>
// )

This is where things get magical. We now have do notation for something that hasn’t even been interpreted yet: it’s pure data.

Next we’d like to define showProgram to prove that what we have is just data:

def showProgram[R: Show](p: Free[CharToy, R]): String =
  p.fold({ r: R => "return " + Show[R].show(r) + "\n" },
    {
      case CharOutput(a, next) =>
        "output " + Show[Char].show(a) + "\n" + showProgram(next)
      case CharBell(next) =>
        "bell " + "\n" + showProgram(next)
      case CharDone() =>
        "done\n"
    })

showProgram(program)
// res8: String = """output A
// bell 
// done
// """

We can manually check that the monad generated using Free satisfies the monad laws:

showProgram(output('A'))
// res9: String = """output A
// return ()
// """

showProgram(pure('A') flatMap output)
// res10: String = """output A
// return ()
// """

showProgram(output('A') flatMap pure)
// res11: String = """output A
// return ()
// """

showProgram((output('A') flatMap { _ => done }) flatMap { _ => output('C') })
// res12: String = """output A
// done
// """

showProgram(output('A') flatMap { _ => (done flatMap { _ => output('C') }) })
// res13: String = """output A
// done
// """

Looking good. Notice the abort-like semantics of done. Also, due to type inference limitation, I was not able to use >>= and >> here.

WFMM:

The free monad is the interpreter’s best friend. Free monads “free the interpreter” as much as possible while still maintaining the bare minimum necessary to form a monad.

Another way of looking at it is that the Free datatype provides a way of building a syntax tree given a container.

One of the reasons the Free datatype is gaining popularity I think is that people are running into the limitation of combining different monads. It’s not impossible with monad transformer, but the type signature gets hairy quickly, and the stacking leaks into various places in code. On the other hand, Free essentially gives up on encoding meaning into the monad. You gain flexibility because you can do whatever in the interpreter function, for instance run sequentially during testing, but run in parallel for production.