Type Systems #21: Algebraic Data Types
(This is part 21 in a series on type systems. You can find part 20 here .)
Last post we defined numbers, now let’s define some operations.
Because I’m funny like that, let’s define multiplication
number * string as a discriminated intersection:
type numberTimesString =
{ prop1: number } &
{ prop2: string };
The important bit is just that each part of the intersection
gets a unique label. string & number is a nonsensical type
in TypeScript, so this is our workaround.
And because I’m funny like that, let’s define addition
number + string as a discriminated union:
type numberPlusString =
| { type: "left"; value: number }
| { type: "right"; value: string };
Again the important bit is the discriminant type property that
makes sure we can tell the variants apart, otherwise string + string
would collapse into just string.
With just these definitions, we can do maths!
2 * string = string + string
Yeah, that’s right. It’s basic arithmetic, but with types!
2 * string is a record containing a boolean and a string;
string + string is something that is either a string tagged
“left” or a string tagged “right”.
I’ll jot down the isomorphism for you:
type TwoTimesString =
{ prop1: boolean } &
{ prop2: string };
type StringPlusString =
| { type: "left"; value: string }
| { type: "right"; value: string };
// TwoTimesString → StringPlusString
const toSum = (p) =>
p.prop1
? { type: "left", value: p.prop2 }
: { type: "right", value: p.prop2 };
// StringPlusString → TwoTimesString
const toProduct = (s) =>
s.type === "left"
? { prop1: true, prop2: s.value }
: { prop1: false, prop2: s.value };
You might wonder where this is useful, but keep in mind that
TwoTimesString comes in many forms in day-to-day programming:
type User = {
isAdmin: boolean;
name: string;
}
It’s the same thing!
6 = 2 * 3
Here, pop quiz for ya. Try to prove that 6 = 2 * 3 by finding
an isomorphism, given these types!
type Two = boolean;
type Three = boolean | null;
type Six = "a" | "b" | "c" | "d" | "e" | "f";
Algebraic Data Types (ADTs), as they are called, are a concept that comes up semi-often when talking about programming languages, even in “normie” circles, because it’s what for example typescript is built around. If you’ve ever wondered why ADTs are called that, now you know! You can do actual algebra with them.
ADTs were actually my
first foray into type theory. There is something deeply satisfying
about inspecting an equation like 2 * string = string + string, and
seeing which types that maps to, in say Java.
It really feels like you’re refactoring half of your codebase in
your head in half a second, just by doing basic maths. Like,
2 * 3 = 6 is such a short statement, but it would
produce a whole lot of code if you were to spell it out.
It’s another tool in the toolbox that occasionally comes in super handy and potentially gives you lots of leverage. You might have a super weird class hierarchy in your codebase, and you don’t quite know how to approach a refactor because everything is so tangled up… But hey! Subclasses are just sums! Can’t that be simplified to a product, like a class with no subclasses, but with a bunch of fields instead?
And you know, treating types like numbers is just fun and such a unique viewpoint.
(This is part 21 in a series on type systems. You can find part 22 here .)