A Early History of Algebraic Data Types

Summary

Been quiet around here! I’ve been putting almost all of my writing time into Logic for Programmers and my whole brain is book-shaped. Trust me, you do not want to read my 2000-word rant on Sphinx post-build LaTeX customization. But I spent the past week in a historical rabbit hole and had to share what I found. It started with Algebraic [Data] Types are not Scary, Actually. The post covers AlgDTs in more detail, but a quick overview is: Product types are things like (Int, Bool) or Dog(name: str, owner: Person, age: Int). They have a value for each field. Almost all modern languages have product types, usually calling them something like “structs” or “records” or “value object” or whatever. Sum types are “tagged unions”, things like Int + Nothing, Result + ErrorType, or Address + Number + Email. They are a choice between several options. The “tag” means that we do not eliminate overlapping choices. Bool + Bool has four possible values, colloquially Left True, Right True, Left False, Right False. Sum types are relatively rare in modern programming languages, outside functional programming and some places like Rust. Where do these get their names? The usual explanation is it comes from their cardinalities (number of possible values): if #T is the cardinality of type T, then #(S + T) == #S + #T and #(S, T) == #S * #T. Try this with Bool + Weekday and (Bool, Weekday) if you feel unsure. But it could instead be that the names come from the fact that sums and products of types act like sums and products of numbers! I think this is pretty known but it doesn’t appear very often in introduction to AlgDTs. For example: Addition over numbers is associative, meaning a + (b + c) == (a + b) + c. This tells us that Int + (String + Null) is isomorphic (≅) to (Int + String) + Null: we can convert values between the two types without losing any useful information. A more interesting example is that AlgDTs follow the distributive property a*(b + c) == a*b + a*c. If we have a value of t...