Free[F, A] is a recursive representation of a program: Return holds a result, Suspend holds one instruction F[A], and FlatMap sequences a prior program with its continuation. The choice of F determines which requests the program may make; interpreting Free must process those suspended layers. section 13.4 section 13.4.1
enum Free[F[_], A]:
case Return(a: A)
case Suspend(s: F[A])
case FlatMap[F[_], A, B](
s: Free[F, A],
f: A => Free[F, B]) extends Free[F, B]
def flatMap[B](f: A => Free[F, B]): Free[F, B] =
FlatMap(this, f)
def map[B](f: A => B): Free[F, B] =
flatMap(a => Return(f(a)))
object Free:
given freeMonad[F[_]]: Monad[[x] =>> Free[F, x]] with
def unit[A](a: => A) = Return(a)
extension [A](fa: Free[F, A])
def flatMap[B](f: A => Free[F, B]) = fa.flatMap(f)
The three constructors separate a completed value, a suspended instruction, and sequencing. map is derived from flatMap and Return, so Free forms a Monad for any F. section 13.10 section 13.4.1
A generic interpreter turns Free[F, A] into F[A] when F has a Monad. Before running, step simplifies FlatMap(Return(x), f) and reassociates nested FlatMaps to the right, leaving Return, Suspend, or a suspended computation followed by a continuation. A specialized trampoline runs Free[Function0, A] directly; Async is Free[Par, A]. section 13.10 section 13.4
Programs describe requests; interpreters choose effects
A Free[Console, A] program does not itself perform console I/O. It can be interpreted to a Reader-like value that ignores printing and supplies fixed input, to State carrying input and output buffers, or to an unsafe console runner. The same program remains a referentially transparent expression while interpretation is a separate decision. section 13.4.3 section 13.10
Free can sequence an algebra’s primitive operations while restricting what a program can do. Files operations produce Free[Files, A], Console operations produce Free[Console, A], and Scala union types can combine those algebras for a program such as cat. This least-power approach improves local reasoning and reuse, but introduces suspension boilerplate, complex union types, and interpreter indirection. section 13.5.1 section 13.6
