Rohit's Blog

This series works through “Data Types à la Carte” by Wouter Swierstra (JFP 18(4), 2008) — a functional pearl that assembles data types and the functions over them from independent pieces, and then does the same trick for a useful class of monads.

I picked it because it’s the strongest candidate I know for a Scala 3 wins post. Haskell has to hand-build a subtyping relation on type constructors, using an extension that isn’t even Haskell 98. Scala 3 has union types and a subtype checker. The question is whether that actually helps, and — spoiler for part 2 — the honest answer is half.

🔗The problem

Write an evaluator for arithmetic expressions and everything is fine:

enum Expr:
  case Val(n: Int)
  case Add(l: Expr, r: Expr)

def eval(e: Expr): Int = e match
  case Val(n)    => n
  case Add(l, r) => eval(l) + eval(r)

Want a second function? Trivial. Add render, add simplify, add depth — none of them touches eval or the data type.

Want a third constructor? Now you’re stuck. Adding Mul to the enum means every existing match becomes non-exhaustive. You must go back and edit eval, render, simplify, and anything else anyone wrote — including code in libraries you don’t control.

Wadler named this the Expression Problem: define a data type by cases such that you can add new cases and new functions, without recompiling existing code, and without losing static type safety.

The two families of language fail it in mirror-image ways. Object-oriented languages add cases easily — a new subclass — and choke on new operations, because every subclass needs the new method. Functional languages add operations easily and choke on new cases. Swierstra’s summary of the Haskell side is exact: new function definitions are fine; new constructors force you to modify existing code.

Scala, sitting in both camps, fails it in both ways depending on which style you pick. A sealed enum behaves exactly like the Haskell above. An open trait hierarchy gives you extensible cases and no exhaustivity checking, which trades the problem for a different one.

🔗Stop fixing the constructors

The move is to make the set of constructors a parameter.

Here’s the type the paper builds around, and it takes a minute:

final case class Fix[F[_]](unfix: F[Fix[F]])

F is a signature — a type constructor describing one layer of the data type, where its type parameter stands for “wherever a sub-expression would go”. Fix then ties the recursive knot, plugging Fix[F] back into F’s hole.

The signatures for our two constructors:

final case class Val[E](n: Int)
final case class Add[E](l: E, r: E)

Val doesn’t use its parameter — a literal has no sub-expressions. Add uses it twice, because addition is binary. Neither knows anything about recursion; Fix supplies that.

So Fix[Val] is the type of expressions that are only literals, and Fix[Add] is the type of expressions that are only additions — which is useless on its own, since it has no base case. Individually these are not interesting. The interesting question is how to combine them.

🔗Coproducts

The answer is to take the coproduct of the signatures — a choice between two layers.

In Haskell that’s a new data type, close to Either but one kind up, with two constructors that inject a left or right layer into the combined signature. Expr (Val :+: Add) is then “either a literal or an addition”, and it’s isomorphic to the ordinary Expr we started with.

And it comes at a cost that the paper is refreshingly blunt about: writing expressions becomes a jumble. Adding two numbers means wrapping every literal in a left-injection, wrapping the addition in a right-injection, and interleaving those with In at every level. The paper’s own example of a two-number sum is an unreadable nest, and it notes the deeper problem — extend the language further and the injections you already wrote are wrong, because Inl and Inr no longer point where they used to.

Most of the rest of the paper is machinery to make that invisible. Which brings us to the first place Scala 3 has something to say.

🔗In Scala, the coproduct is a union

Scala 3 has union types. A | B is the type of values that are either an A or a B — and crucially it is untagged. There is no Inl, no Inr, no wrapper. A Val is a Val | Add, by subtyping.

Unions work on types, not type constructors, but that’s what type lambdas are for:

type :+:[F[_], G[_]] = [A] =>> F[A] | G[A]

Now Val :+: Add is a signature, and Fix[Val :+: Add] is our expression type:

type Sig = Val :+: Add
type E   = Fix[Sig]

And the horrible nested example becomes… just the constructors:

val addExample: E = Fix(Add(Fix(Val(118)), Fix(Val(1219))))

No injections. Val[E] is already a subtype of Val[E] | Add[E], so there is nothing to inject. Extend the language later and this expression still typechecks unchanged, because subtyping doesn’t care what else joined the union.

The paper spends its entire fourth and fifth sections building machinery to recover exactly this. In Scala that machinery has nothing to do.

🔗`:<:` is `<:<`

The centrepiece of that machinery is a type class expressing “signature sub embeds in signature sup”, with an injection function. It has three instances — reflexivity, injecting into the left of a coproduct, and recursively injecting into the right — and they overlap, which puts the whole thing outside Haskell 98 and requires an extension.

It also has a documented limitation. Because the recursive instance only searches the right-hand side of a coproduct, a signature nested on the left can’t be found even when an injection obviously exists. The paper’s guidance is to declare the coproduct operator right-associative and never nest explicitly.

In Scala, that relation is subtyping, and the evidence for it is <:< — which the compiler supplies whenever the subtyping actually holds:

def value[F[_]](n: Int)(using ev: Val[Fix[F]] <:< F[Fix[F]]): Fix[F] =
  Fix(ev(Val(n)))

def add[F[_]](l: Fix[F], r: Fix[F])(using ev: Add[Fix[F]] <:< F[Fix[F]]): Fix[F] =
  Fix(ev(Add(l, r)))

Read using ev: Val[Fix[F]] <:< F[Fix[F]] as “any signature F that supports literals” — which is precisely how the paper asks you to read its constraint.

Three things fall out, and they’re the reason I wanted to write this series:

No overlapping instances. There are no instances at all. <:< is discharged by the subtype checker.

No nesting limitation. Subtyping is associative and commutative up to equivalence, so Val is findable inside (Val | Add) | Mul exactly as easily as inside Val | (Add | Mul). The paper’s caveat evaporates.

No search. Haskell walks a chain of instances to build a composite injection out of Inl and Inr. Scala checks a subtyping judgement. The injection function is the identity, because untagged means there is nothing to wrap.

🔗Two things that get worse

I promised the honest version, so here are the costs — both real.

Duplicates collapse. Val | Val is Val. The paper discusses what happens with a coproduct of a signature with itself, and which of the two possible injections gets chosen; it concludes the ambiguity is harmless because nothing downstream inspects position. In Scala the question can’t be asked — the type is idempotent. Mostly that’s a simplification, but it does mean you cannot have two distinguishable copies of the same signature in one language, which Haskell’s tagged version permits.

Inference widens unions. Scala 3 will generalise an inferred union to a common supertype in a lot of positions, so:

val x = add(value(30000), value(1330))   // what is the type of x?

is not going to give you what you want without help. You need the annotation:

val x: Fix[Val :+: Add] = add(value(30000), value(1330))

Which is exactly the discipline the paper demands, for a different reason — there, the signature is what lets the compiler pick the injection, and Swierstra emphasises that without it the compiler has no hope of guessing. Both languages require the type annotation; Haskell to resolve an injection, Scala to prevent widening. I find that pleasing. The annotation isn’t an artefact of either encoding; it’s the place where you say which language you’re writing in.

I have not compiled any of this. There’s no JVM on the machine I drafted the series on, so everything here is reasoned from the specification rather than checked. The <:< argument I’m confident about — it’s ordinary subtyping, and <:< is defined precisely so that evidence exists whenever the relation holds. The union-widening behaviour I’m confident about in outline and not in every position. Part 2 contains a claim I’m genuinely unsure of, and I’ve flagged it there rather than smoothing it over.

🔗What we can’t do yet

We have a data type assembled from independent pieces, and — in Scala — we can write values of it without any injection noise at all.

What we can’t do is interpret it. eval needs to handle both cases, and the whole point is that neither Val nor Add should know the other exists. So evaluation has to be assembled from pieces too, one per signature, combined automatically when signatures are combined.

In Haskell that’s a type class with an instance per functor and a recursive instance for coproducts, and it is completely straightforward.

In Scala it is the hard part, and it’s where the untagged coproduct starts charging rent.

Next: Part 2 — Modular algebras, and where Scala gets harder.

🔗Sources

Swierstra, Wouter. Data Types à la Carte. Journal of Functional Programming 18(4), 423–436, 2008. Functional pearl. The Expr f = In (f (Expr f)) encoding, the coproduct of signatures, the :≺: class with its three overlapping instances and right-nesting limitation, and the smart constructors are all his. Available from the author.
Wadler, Philip. The Expression Problem. 1998 — the problem statement.
Meijer, Erik, Maarten Fokkinga & Ross Paterson. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. 1991 — fixed points of functors, which the paper notes are long-standing folklore.

The Scala 3 translation, the union-type coproduct, and the argument that <:< subsumes the :≺: class along with its nesting limitation are mine.