Rohit's Blog

Occasional writing on software engineering.

Data Types à la Carte, Part 3: Adding Cases Without Touching Code

scalatype-systems

Following “Data Types à la Carte” by Wouter Swierstra (JFP 2008). Part 1 built expressions as fixed points of a signature; part 2 assembled interpreters from independent algebras, and worked out which half of the machinery Scala 3 gets for free and which half it doesn’t.

All of that was setup. This post spends it.

🔗Adding multiplication

The test the Expression Problem sets: add a constructor without editing existing code.

A new signature and its functor instance:

final case class Mul[E](l: E, r: E)

given Functor[Mul] with
  def map[A, B](fa: Mul[A])(f: A => B): Mul[B] = Mul(f(fa.l), f(fa.r))

How to evaluate it:

given Eval[Mul] with
  def alg(fa: Mul[Int]): Int = fa.l * fa.r

And a smart constructor, in the style of part 1 — “any signature that supports multiplication”:

extension [F[_]](l: Fix[F])
  def *(r: Fix[F])(using ev: Mul[Fix[F]] <:< F[Fix[F]]): Fix[F] =
    Fix(ev(Mul(l, r)))

That’s the entire change. Three declarations, in a new file, and:

val x: Fix[Val :+: Add :+: Mul] = value(80) * value(5) + value(4)
// eval(x) == 404

Nothing was edited. Not the Fix type, not Val, not Add, not their functor or eval instances, not the fold. Mul was added from outside, in code that the original author never saw, and existing expressions still compile and still mean what they meant.

That is the thing the paper is for, and it’s worth sitting with for a second, because it’s the half of the Expression Problem that functional languages normally cannot do at all.

🔗Assembling a language, not extending one

The paper makes a second point here that I think is easy to skim past, and it’s the better one.

You can also write:

val y: Fix[Val :+: Mul] = value(6) * value(7)

A language with literals and multiplication and no addition. Not a subset checked at runtime — a type in which addition is not expressible.

So this isn’t only about extending a language. Once you have a menu of building blocks, you assemble the data type you want by choosing from it, and the type records exactly what’s on the plate. Swierstra notes that this isn’t achievable even with the proposed language extensions for open data types that existed at the time.

The payoff shows up again in part 4, where the same trick applied to monads means a program’s type says which effects it may use — and a type that permits reading files but not writing them is a genuinely useful thing to be able to write down.

🔗A second function, written by recursion

Adding functions was never the hard part, but the paper’s pretty-printer contains a wrinkle worth reproducing because it catches people.

The obvious class is one whose method renders a layer whose children are expressions in the same signature. That type is too tight, and the reason is subtle: rendering an addition means recursively rendering its children, and those children need not themselves be additions — they might be literals. Requiring the sub-expressions of an Add to be Adds is nonsense.

The fix is to loosen the recursive occurrence so children may live in any renderable signature:

trait Render[F[_]]:
  def render[G[_]: Render](fa: F[Fix[G]]): String

def pretty[F[_]](e: Fix[F])(using F: Render[F]): String =
  F.render(e.unfix)

Note the method’s own type parameter G with its own constraint — the signature of the children is independent of the signature of the node. In Haskell that’s a constrained polymorphic method inside a class; in Scala it’s a polymorphic method with a context bound, which is the same idea and needs no extension.

Then the instances read exactly like the ordinary pretty-printer you’d have written on day one:

given Render[Val] with
  def render[G[_]: Render](fa: Val[Fix[G]]): String = fa.n.toString

given Render[Add] with
  def render[G[_]: Render](fa: Add[Fix[G]]): String =
    s"(${pretty(fa.l)} + ${pretty(fa.r)})"

given Render[Mul] with
  def render[G[_]: Render](fa: Mul[Fix[G]]): String =
    s"(${pretty(fa.l)} * ${pretty(fa.r)})"

Plus the coproduct case, which dispatches to whichever side it has — with all the caveats from part 2 about how that’s spelled.

pretty(x)   // "((80 * 5) + 4)"

A new function over a data type that was assembled à la carte, again without editing anything.

Two things I’d flag. First, this one is written by direct recursion, not as a fold — the paper deliberately shows both styles, and direct recursion is the right choice when the function is naturally structural rather than a reduction. Second, Render is exactly the shape of a Show typeclass, which means the pattern here is not exotic: it’s what you’d do anyway, one signature at a time.

🔗Going the other way: projection

inj embeds a small signature into a bigger one. Its partial inverse asks the opposite question — given a layer of the big signature, is it in fact a Mul?

def prj[F[_], G[_]](fa: F[Fix[F]]): Option[G[Fix[F]]]

In Haskell this is a second method on the subtyping class, defined alongside the injections. In Scala with untagged unions it is a type test — which, for concrete signatures, is just a pattern match on the class:

def matchAs[F[_], G[_]](e: Fix[F])(using tt: TypeTest[F[Fix[F]], G[Fix[F]]]): Option[G[Fix[F]]] =
  e.unfix match
    case tt(g) => Some(g)
    case _     => None

This is the same TypeTest that made part 2 awkward, and here it’s doing exactly what it’s for — recovering a specific case from an untagged union at runtime. Same mechanism, opposite verdict: bad when you wanted structural induction, fine when you wanted a downcast.

🔗Rewriting expressions

With projection you can pattern-match through a coproduct, and the paper’s example is a rewrite rule: distributing multiplication over addition, a × (c + d) becomes (a × c) + (a × d).

The shape is: project the outer layer as a Mul; project that Mul’s right child as an Add; if both succeed, rebuild. In Haskell that’s three lines in the Maybe monad. In Scala it’s a for-comprehension over Option:

def distr[F[_]](e: Fix[F])(using
  mul: TypeTest[F[Fix[F]], Mul[Fix[F]]],
  add: TypeTest[F[Fix[F]], Add[Fix[F]]],
  emb1: Mul[Fix[F]] <:< F[Fix[F]],
  emb2: Add[Fix[F]] <:< F[Fix[F]]
): Option[Fix[F]] =
  for
    Mul(a, b) <- matchAs[F, Mul](e)
    Add(c, d) <- matchAs[F, Add](b)
  yield (a * c) + (a * d)

The constraint list is the honest cost of doing this in Scala — four using parameters where Haskell needs two class constraints, because we need both the embeddings (to rebuild) and the type tests (to take apart), and unions give us the first for free while making the second explicit.

But look at the body. It says: if this is a multiplication whose right side is an addition, distribute. The signature is noisy; the logic is exactly the rewrite rule. And the function works for any signature containing both Mul and Add, including ones defined later by someone else.

Fold distr over an expression with a suitable algebra and you have a rewriting pass, built from a rule that knows about two constructors and is agnostic about every other constructor in the language. For anyone who has written an optimiser and had to add a case to a giant match every time the AST grew, that should look appealing.

🔗Taking stock

Both directions of the Expression Problem, satisfied:

  • New cases — Mul, added from outside, no edits.
  • New functions — Render, distr, added from outside, no edits.
  • Static type safety — retained throughout; Fix[Val :+: Mul] cannot contain an addition.
  • À la carte assembly — pick your constructors; the type records the choice.

And the cost, stated plainly, because a post that only lists benefits isn’t worth much:

Every expression needs a type annotation. Every function carries constraints proportional to how many signatures it mentions. The values are wrapped in Fix at every level, which is a real allocation and a real indirection. And in Scala specifically, part 2’s dispatch problem means the coproduct instances are either unsafe or constraint-heavy.

Would I build a production AST this way? For a compiler with a fixed grammar, no — a sealed enum with exhaustivity checking is better in every respect that matters, and the Expression Problem isn’t a problem when you own all the code.

Where it earns its keep is when the set of cases is genuinely open: a plugin architecture, a DSL that third parties extend, an effect system where libraries contribute operations. And that last one is the subject of part 4 — where the same technique applied to monads turns out to be something most Scala developers have used without knowing where it came from.

Next: Part 4 — Free monads, and the library you already use.

🔗Sources

  • Swierstra, Wouter. Data Types à la Carte. JFP 18(4), 423–436, 2008. Adding Mul without modification, the à la carte assembly point, the Render class with its generalised recursive type, the prj projection, and the distributivity rewrite are all his. Available from the author.
  • Löh, Andres & Ralf Hinze. Open data types and open functions. 2006 — the language extension the paper compares against.

The Scala 3 translation, and the observation that TypeTest is the right tool for projection even though it was the wrong tool for algebra assembly, are mine. As in the rest of the series, none of this has been compiled — see the warning in part 2.