I've spent a lot of time reviewing code from developers moving into high-level functional Scala, and there's a recurring pattern when they hit Free Monads: they think it's just a more verbose way of doing Dependency Injection. They'll tell me, "Why can't I just define a trait for my repository and inject a mock implementation for my tests?"

Free Monads Aren't Just Dependency Injection

If you use standard DI—say, passing a UserRepository trait into a service—you are binding your business logic to the execution of those effects. When you call repo.save(user), you're triggering a side effect immediately. The "program" is the act of calling the functions.

The Free Monad pattern is fundamentally different because it turns your program into a data structure. Instead of executing a save operation, you are building a tree of instructions that says "I would like to save this user."

Why does that distinction matter? Because when your program is just data, you can do things you can't do with DI. You can inspect the program, optimize it (like batching multiple database reads into one), or run the exact same sequence of logic through three different interpreters without ever changing a line of business code. You aren't injecting a dependency; you're separating the intent of the program from its execution.

Turning Logic Into Data via Algebra

To get this working, we first define our "Algebra"—basically a set of commands our program can issue. Let's imagine we're building a simple Order Processing system. We don't want the logic to know if we're using Postgres, MongoDB, or a HashMap in memory.

case class Order(id: String, amount: Double)

// This is our Algebra
sealed trait OrderOp[A] {
  case class GetOrder(id: String) extends OrderOp[Order]
  case class SaveOrder(order: Order) extends OrderOp[Unit]
  case class LogMessage(msg: String) extends OrderOp[Unit]
}

Now, the "Free" part comes in. By wrapping this algebra in Free (which is essentially a recursive structure that allows us to chain these operations using flatMap), we can write a program that looks like standard imperative code but is actually just a nested object.

import cats.free.Free
import cats.impl.applicativeFunctors.Function1

// A helper to lift our algebra into the Free Monad
def getOrder(id: String): Free[OrderOp, Order] = Free.liftF(OrderOp.GetOrder(id))
def saveOrder(order: Order): Free[OrderOp, Unit] = Free.liftF(OrderOp.SaveOrder(order))
def logMsg(msg: String): Free[OrderOp, Unit] = Free.liftF(OrderOp.LogMessage(msg))

// This is our "Program". Note that NO actual DB calls happen here.
def processOrder(id: String): Free[OrderOp, Unit] = {
  for {
    order <- getOrder(id)
    _     <- logMsg(s"Processing order ${order.id}")
    _     <- saveOrder(order.copy(amount = order.amount * 0.9)) // 10% discount
    _     <- logMsg("Discount applied and saved")
  } yield ()
}

Separating the Algebra from the Interpreter

At this point, processOrder is just a value. It's a blueprint. To actually make it do something, we need an interpreter. This is where we map our OrderOp types to actual effects, like IO or Future.

I usually think of the interpreter as the "compiler" for my DSL. I can write one for production and one for testing.

import cats.effect.IO

// The Production Interpreter
def runProd[A](op: OrderOp[A]): IO[A] = op match {
  case OrderOp.GetOrder(id) => IO.println(s"Querying DB for $id").as(Order(id, 100.0))
  case OrderOp.SaveOrder(o) => IO.println(s"Writing $o to Postgres")
  case OrderOp.LogMessage(m) => IO.println(s"[LOG]: $m")
}

// To run it, we use the 'foldMap' method provided by Free
val productionProgram = processOrder("order-123").foldMap(runProd)

If I wanted to test this, I wouldn't need a complex mocking framework. I'd just write a runTest interpreter that uses a State monad to track changes in a local map. The business logic in processOrder remains untouched and blissfully unaware of how it's being executed.

📋 Practical Task

Implement a Memory-Based FileSystem Interpreter

You are given a FileOp algebra that describes basic file system operations. Your task is to implement a runMemory interpreter that uses a scala.collection.mutable.Map to simulate a file system in memory, allowing you to test file logic without hitting the actual disk.

import cats.free.Free
import cats.effect.IO

sealed trait FileOp[A] {
  case class ReadFile(path: String) extends FileOp[String]
  case class WriteFile(path: String, content: String) extends FileOp[Unit]
  case class DeleteFile(path: String) extends FileOp[Unit]
}

object FileSystem {
  def readFile(path: String): Free[FileOp, String] = Free.liftF(FileOp.ReadFile(path))
  def writeFile(path: String, content: String): Free[FileOp, Unit] = Free.liftF(FileOp.WriteFile(path, content))
  def deleteFile(path: String): Free[FileOp, Unit] = Free.liftF(FileOp.DeleteFile(path))
}

// TODO: Implement this function
def runMemory[A](op: FileOp[A], storage: mutable.Map[String, String]): IO[A] = {
  op match {
    // Handle ReadFile: return value from map or throw error if missing
    // Handle WriteFile: put value into map
    // Handle DeleteFile: remove key from map
  }
}

// Test your implementation with this program:
val program = for {
  _ <- FileSystem.writeFile("test.txt", "Hello Free Monads!")
  content <- FileSystem.readFile("test.txt")
  _ <- FileSystem.deleteFile("test.txt")
} yield content

Requirements:

• The ReadFile case must return the string stored in the map for the given path.
• The WriteFile case must update the map and return IO.unit.
• The DeleteFile case must remove the entry from the map and return IO.unit.
• The final output of program.foldMap(op => runMemory(op, myMap)) should be an IO that resolves to "Hello Free Monads!".