Scala Free Monads, in depth: programs as data, interpreters as natural transformations, and when Free beats tagless final

The idea: separate what from how

Ordinary effectful code mixes two concerns: the business logic (check the balance, debit one account, credit another) and the mechanism (which database, which transaction, which retries). Free monads split them. You define an algebra, a sealed set of case classes, one per operation, each tagged with the type of value it returns. A program is then a data structure built from those operations, chained with flatMap. An interpreter is a function that maps each operation to an action in some target monad, such as Id, State or IO.

Free is called free because it gives you a lawful monad for any type constructor F, with no requirements on F at all. All the monadic structure comes from Free; F only has to describe operations. You pay for that generality later, when you supply an interpreter into a real monad.

Building Free from scratch

Free needs only three shapes: a finished value, a suspended operation, and a continuation that says what to do with a result.

sealed trait MyFree[F[_], A] {
  def flatMap[B](f: A => MyFree[F, B]): MyFree[F, B] = FlatMapped(this, f)
  def map[B](f: A => B): MyFree[F, B] = flatMap(a => Pure(f(a)))
}
final case class Pure[F[_], A](a: A) extends MyFree[F, A]
final case class Suspend[F[_], A](fa: F[A]) extends MyFree[F, A]
final case class FlatMapped[F[_], E, A](sub: MyFree[F, E], k: E => MyFree[F, A]) extends MyFree[F, A]

// Naive interpreter: correct, but recursion depth grows with program length.
def runNaive[F[_], G[_], A](prog: MyFree[F, A], nt: [X] => F[X] => G[X])(using M: cats.Monad[G]): G[A] =
  prog match {
    case Pure(a)              => M.pure(a)
    case Suspend(fa)          => nt(fa)
    case FlatMapped(sub, k)   => M.flatMap(runNaive(sub, nt))(e => runNaive(k(e), nt))
  }

Notice that flatMap does no work. It allocates a node. A for-comprehension over MyFree therefore produces a tree whose leaves are operations and whose internal nodes are continuations. The naive interpreter recurses through that tree, which works for short programs and overflows the stack for long loops, especially left-nested chains such as a fold that builds ((a flatMap f) flatMap g) flatMap h. Cats solves this by reassociating nested binds as it steps and delegating the loop to the target monad's tailRecM.

A ledger with Cats Free

import cats.{~>, Id}
import cats.data.State
import cats.free.Free
import cats.free.Free.liftF
import scala.collection.mutable

sealed trait AccountOp[A]
final case class Balance(id: String)              extends AccountOp[Long]
final case class Debit(id: String, amount: Long)  extends AccountOp[Unit]
final case class Credit(id: String, amount: Long) extends AccountOp[Unit]

type Account[A] = Free[AccountOp, A]

def balance(id: String): Account[Long]            = liftF(Balance(id))
def debit(id: String, amt: Long): Account[Unit]   = liftF(Debit(id, amt))
def credit(id: String, amt: Long): Account[Unit]  = liftF(Credit(id, amt))

def transfer(from: String, to: String, amt: Long): Account[Either[String, Unit]] =
  balance(from).flatMap { b =>
    if (b < amt) Free.pure[AccountOp, Either[String, Unit]](Left(s"insufficient funds in $from"))
    else for {
      _ <- debit(from, amt)
      _ <- credit(to, amt)
    } yield (Right(()): Either[String, Unit])
  }

The smart constructors balance, debit and credit lift each operation into Free with liftF, so the business logic reads like ordinary monadic code. Calling transfer("alice", "bob", 30) executes nothing. It returns a value describing a balance check, a branch and two writes.

Interpreters are natural transformations, written AccountOp ~> G: a function that works for every result type A. Here are two. The first is impure and convenient for demos; the second is pure and ideal for tests.

def unsafeInterpreter(store: mutable.Map[String, Long]): AccountOp ~> Id =
  new (AccountOp ~> Id) {
    def apply[A](op: AccountOp[A]): Id[A] = op match {
      case Balance(id)     => store.getOrElse(id, 0L)
      case Debit(id, amt)  => store.update(id, store.getOrElse(id, 0L) - amt)
      case Credit(id, amt) => store.update(id, store.getOrElse(id, 0L) + amt)
    }
  }

final case class World(balances: Map[String, Long], log: Vector[String])
type Ledger[A] = State[World, A]

val pureInterpreter: AccountOp ~> Ledger = new (AccountOp ~> Ledger) {
  private def adjust(id: String, d: Long): Ledger[Unit] =
    State.modify(w => w.copy(balances = w.balances.updated(id, w.balances.getOrElse(id, 0L) + d)))
  def apply[A](op: AccountOp[A]): Ledger[A] = op match {
    case Balance(id)     => State.inspect(_.balances.getOrElse(id, 0L))
    case Debit(id, amt)  => adjust(id, -amt)
    case Credit(id, amt) => adjust(id, amt)
  }
}

val (world, result) =
  transfer("alice", "bob", 30).foldMap(pureInterpreter).run(World(Map("alice" -> 100L), Vector.empty)).value
// result == Right(()), world.balances == Map("alice" -> 70, "bob" -> 30)

The pattern match returns a Long for Balance where the signature says A; Scala 3 accepts this because matching on a case class that extends AccountOp[Long] refines A to Long. In Scala 2 you may need a cast in some cases, which is one of the paper cuts of the encoding.

How foldMap runs, and why it is stack safe

foldMap walks the program one step at a time. At each step it normalises the head of the tree: a Pure finishes, a Suspend is handed to the interpreter, and nested FlatMapped nodes are reassociated to the right so the next operation is always at the front. The loop is expressed through the target monad's tailRecM, which takes a step function returning either continue with a new state or done with a result.

So Free is exactly as stack safe as your target monad's tailRecM. Cats' State is built on Eval and is stack safe, as are Cats Effect IO and Id. A hand-written monad whose tailRecM simply recurses will overflow on long programs no matter how carefully Free is implemented. If you write a custom target monad, test it with a loop of a million steps before trusting it.

Each step allocates: one node per flatMap when building, plus closures and interpreter calls when running. For business workflows dominated by I/O this is noise. For tight inner loops it is a real overhead compared with calling methods directly, which is one reason performance-sensitive libraries moved to other encodings.

Composing algebras with EitherK and InjectK

Real programs need more than one vocabulary. Suppose every transfer must also write an audit event. Rather than adding audit operations to AccountOp, define a second algebra and combine the two with EitherK, the coproduct of type constructors. InjectK lets each algebra's smart constructors target any coproduct that contains it.

import cats.InjectK
import cats.data.EitherK

sealed trait AuditOp[A]
final case class Record(event: String) extends AuditOp[Unit]

class Accounts[F[_]](implicit I: InjectK[AccountOp, F]) {
  def balance(id: String): Free[F, Long]           = Free.liftInject[F](Balance(id))
  def debit(id: String, amt: Long): Free[F, Unit]  = Free.liftInject[F](Debit(id, amt))
  def credit(id: String, amt: Long): Free[F, Unit] = Free.liftInject[F](Credit(id, amt))
}
class Audit[F[_]](implicit I: InjectK[AuditOp, F]) {
  def record(e: String): Free[F, Unit] = Free.liftInject[F](Record(e))
}

type App[A] = EitherK[AccountOp, AuditOp, A]

def auditedTransfer(from: String, to: String, amt: Long)
                   (implicit A: Accounts[App], L: Audit[App]): Free[App, Boolean] =
  for {
    b  <- A.balance(from)
    ok =  b >= amt
    _  <- if (ok) A.debit(from, amt).flatMap(_ => A.credit(to, amt)) else Free.pure[App, Unit](())
    _  <- L.record(s"transfer $from->$to $amt ok=$ok")
  } yield ok

val auditInterpreter: AuditOp ~> Ledger = new (AuditOp ~> Ledger) {
  def apply[A](op: AuditOp[A]): Ledger[A] = op match {
    case Record(e) => State.modify(w => w.copy(log = w.log :+ e))
  }
}

implicit val accounts: Accounts[App] = new Accounts[App]
implicit val audit: Audit[App]       = new Audit[App]
val appInterpreter: App ~> Ledger = pureInterpreter or auditInterpreter

pureInterpreter or auditInterpreter builds an interpreter for the coproduct from interpreters for its parts. Three or more algebras nest as EitherK[A, EitherK[B, C, *], *], which works but becomes noisy, and type inference errors in this area are notoriously hard to read. That boilerplate is the strongest practical argument for tagless final, where combining capabilities is just adding another constraint.

Testing by interpretation

Testing is where Free pays off most directly. Because the program is a value, a test interpreter can record every operation, return canned results, or fail on demand, with no mocking framework. The World state above already captures balances and the audit log, so a test is a plain assertion.

val start = World(Map("alice" -> 20L), Vector.empty)
val (end, ok) = auditedTransfer("alice", "bob", 30).foldMap(appInterpreter).run(start).value
assert(!ok)
assert(end.balances == Map("alice" -> 20L))               // nothing moved
assert(end.log == Vector("transfer alice->bob 30 ok=false"))

Fault injection is equally direct: an interpreter into Either[String, *] can fail the second Debit it sees, which lets you check what a program does when a write fails halfway, a case that is hard to provoke against a real database.

FreeApplicative: analyse before you run

A monadic program can choose its next step based on a previous result, so you cannot know all of its operations without running it. If your operations are independent, cats.free.FreeApplicative gives up flatMap in exchange for a structure that can be fully inspected in advance. That enables batching, deduplication, parallel execution or permission checks before any I/O.

import cats.data.Const
import cats.free.FreeApplicative
import cats.syntax.all._

type Plan[A] = FreeApplicative[AccountOp, A]
def bal(id: String): Plan[Long] = FreeApplicative.lift(Balance(id))

val totalExposure: Plan[Long] = (bal("alice"), bal("bob"), bal("alice")).mapN(_ + _ + _)

type Keys[A] = Const[Set[String], A]
val keysOf: AccountOp ~> Keys = new (AccountOp ~> Keys) {
  def apply[A](op: AccountOp[A]): Keys[A] = op match {
    case Balance(id)    => Const(Set(id))
    case Debit(id, _)   => Const(Set(id))
    case Credit(id, _)  => Const(Set(id))
  }
}

val needed: Set[String] = totalExposure.foldMap(keysOf).getConst   // Set("alice", "bob")
// Fetch both balances in one round trip, then run with a cached interpreter.

Folding into Const accumulates a monoid instead of running anything, so the analysis is just another interpreter. A real system would use the key set to issue one batched query, then run the plan with an interpreter that reads from the prefetched map. Applicative versus monadic power is explained in functors and applicatives.

Free, tagless final or a concrete effect type

Use Free when the program as a value is the point: workflow engines that persist and resume steps, DSLs that must be validated, optimised or rendered as documentation, and request batching. Use tagless final or a concrete effect type for ordinary application services. Many teams that adopted Free in the late 2010s migrated to Cats Effect directly. The wider landscape is surveyed in effect systems compared.

Failure modes

• Stack overflow at runtime. The target monad has a recursive tailRecM. Test interpreters on long loops.
• Non-exhaustive interpreters. Adding an operation to a sealed algebra without updating every interpreter produces a match warning that is easy to ignore. Compile with warnings as errors.
• Leaky algebras. Operations such as RunSql(query) expose the mechanism and defeat the point. Model domain operations, not infrastructure calls.
• Hidden effects in smart constructors. Reading the clock or generating IDs while building the program makes the description impure. Make those operations in the algebra too.
• Interpreter drift. The test interpreter and the production interpreter disagree on semantics such as missing accounts. Share law-style tests that run against both.

What to do next

1. Write a three-operation algebra for a domain you know and two interpreters, one into State and one into IO.
2. Run a 1,000,000-step loop through foldMap with each interpreter to confirm stack safety.
3. Add a second algebra and combine it with EitherK and InjectK, then decide whether the boilerplate is acceptable for your team.
4. Rewrite one independent section as FreeApplicative and build an analysis interpreter into Const.
5. Implement the same domain in tagless final and compare readability, compile errors and a simple benchmark.
6. Keep Free only where inspecting or rewriting programs before execution delivers real value.