Algebraic Data Types
Products hold several things at once; sums hold exactly one of several things. The word "algebraic" is literal — cardinalities multiply for products and add for sums — and that arithmetic is the fastest way to tell whether a data model can represent states that must never exist.
Why are enums with payloads called "algebraic", and when should I reach for one instead of a struct with a few optional fields?
A closed set of variants, each carrying a fixed product of fields. In the compiler this is a tag plus a union of the variant payload layouts, and the tag is the only thing a match is permitted to branch on. The representation exists to answer one question that a record with optional fields cannot answer: which combination of fields is actually present, decidably, at every point.
Every phase downstream may assume the variant set is closed — no value of the type exists outside the declared variants — which is precisely the assumption [[exhaustiveness-checking]] cashes in. Open the set and the assumption is void: a public non-exhaustive enum, an extensible class hierarchy, or a value crossing a deserialization boundary all withdraw it, and any match compiled under the closed assumption must then be given a fallback arm.
Key points
- There are two ways to compose types: products require all the parts, sums require exactly one of them.
- The name is literal — product cardinalities multiply, sum cardinalities add, and the usual algebraic identities hold.
- Comparing the count of representable states against the count of domain states measures how much of your correctness is riding on convention.
- A sum type is closed by declaration, which is what makes exhaustiveness checking possible and what makes adding a variant a breaking change.
ResultandOptionare ordinary sums with no special checker support, which is exactly why they compose with everything else.- Sums need ergonomic support — a propagation operator and exhaustiveness checking — or they degrade into a match pyramid and an
unwrap. - A struct of optional fields is what a sum turns into when the language lacks one, and the excess states it admits are a recurring source of production bugs.
Two ways to combine types
There are exactly two primitive ways to build a compound type. You can take several types and require all of them: a record, a tuple, a struct, a class with fields. That is a product. Or you can take several types and require exactly one of them: an enum with payloads, a tagged union, a data declaration with several constructors. That is a sum.
Every mainstream language has had products since the 1960s. Sums are the ones that keep getting left out, and their absence is why so many codebases contain a struct with five optional fields, a comment explaining which combinations are valid, and a bug in the one combination the comment did not mention.
Recursion is the third ingredient and it comes free: a variant may carry the type being defined, which gives lists, trees and expression ASTs. That is not a coincidence either — the AST in [[abstract-syntax-tree]] is the canonical algebraic data type, and languages with good sum types tend to have unusually pleasant compiler implementations for exactly this reason.
1// Product: every field, always.2struct Point { x: f64, y: f64 }3 4// Sum: exactly one variant, and its payload.5enum Shape {6 Circle { r: f64 },7 Rect { w: f64, h: f64 },8 Empty,9}10 11// Recursive sum: the canonical AST.12enum Expr {13 Lit(i64),14 Add(Box<Expr>, Box<Expr>),15 Neg(Box<Expr>),16}Note what is impossible to write: a Shape with both r and w, or with neither. The illegal states are not merely discouraged, they have no representation.
Why "algebraic": the cardinalities really do add and multiply
Count the values a type has. bool has 2. () — the empty product — has 1. never — the empty sum, with no variants at all — has 0. Now count compounds. A struct of a bool and a bool has 2 × 2 = 4 values, because every combination of the fields is a distinct value. An enum of a bool variant and a bool variant has 2 + 2 = 4 values, because you get one side or the other, tagged.
That is the whole of the name. Products multiply, sums add, and the algebra behaves: A × 1 = A (a struct with an extra unit field carries no more information), A + 0 = A (a variant that cannot be constructed contributes nothing), and A × (B + C) = A × B + A × C (a record containing a two-variant enum is the same information as a two-variant enum of records — which is a refactoring you will do by hand often, now that you can see it is an identity).
The reason to care is not elegance, it is a diagnostic. Count the states your data model can represent and count the states your domain actually has. If the first number is larger, the difference is the set of states you now have to exclude by convention, by validation, or by a comment — and each one is a bug waiting for the branch that forgot.
The classic example is a request with loading: boolean, data: T | null and error: Error | null. That is 2 × (|T| + 1) × 2 representable states. The domain has three: loading, loaded with data, failed with an error. Everything else — loading *and* errored, loaded with neither data nor error — is representable, and some of it will happen.
| Type | Cardinality | What the count tells you |
|---|---|---|
never (empty sum) | 0 | No value exists. Useful as a return type and as an exhaustiveness witness. |
() / void (empty product) | 1 | Exactly one value, carrying no information. The multiplicative identity. |
bool | 2 | The smallest interesting type. |
struct { a: bool, b: bool } | 2 × 2 = 4 | Products multiply: every combination is a distinct value. |
enum { A(bool), B(bool) } | 2 + 2 = 4 | Sums add: one side or the other, and the tag says which. |
Option<bool> | 1 + 2 = 3 | The classic sum. Absence is one of the three states, not a fourth thing beside them. |
{ loading: bool, data: T?, err: E? } | 2 × (|T|+1) × (|E|+1) | Far more than the three states the domain has. The excess is the bug surface. |
enum { Loading, Loaded(T), Failed(E) } | 1 + |T| + |E| | Exactly the domain. Nothing to exclude by convention. |
Result and Option: the two sums worth knowing by name
? operator is Rust's, and it desugars to a match plus an early return with a From conversion on the error — see [[desugaring]]. Haskell reaches the same ergonomics through do notation over a monad, Swift through try with a thrown-error channel that is a sum under the hood, and Go through the explicit if err != nil that it deliberately did not sugar. The data type is portable; the ergonomics are not, and a Result type in a language with neither operator nor exhaustiveness checking is worse than the exceptions it replaced.Result<T, E> = Ok(T) | Err(E) and Option<T> = Some(T) | None are ordinary sum types with no special status in the type checker. That is the whole point of them: because they are ordinary data, everything that works on data works on them — they compose, they can be stored, returned, put in a list, mapped over, and combined without any language machinery.
Contrast with exceptions, which are a control-flow construct rather than data. An exception cannot be stored in a struct, cannot be returned from a function that also returns normally, and does not appear in the signature unless the language forces it to — which is the argument that [[effect-systems]] picks up. A Result appears in the signature by construction, which means the caller cannot ignore the failure path without saying so.
The cost is honest and worth stating. Every call site that returns a Result must handle or propagate it, and without syntactic support that is a pyramid of matches. Languages that lean on sums for errors therefore all grow an operator to make propagation one character: ? in Rust, do notation in Haskell, try in Swift. Where no such operator exists, Result becomes a burden rather than a discipline, and a codebase adopting it without one usually reverts.
And the failure mode is the same one as anywhere else in this module: Result in a language with no [[exhaustiveness-checking]] degrades into a value people call .unwrap() on. The sum type is only half of the mechanism.
1enum Result<T, E> { Ok(T), Err(E) }2 3fn parse_port(s: &str) -> Result<u16, ParseError> {4 let n: u32 = s.parse()?; // `?` returns early on Err, unwraps on Ok5 if n > 65535 { return Err(ParseError::OutOfRange) }6 Ok(n as u16)7}8 9// Because it is ordinary data, it composes like data:10let ports: Vec<Result<u16, ParseError>> = inputs.iter().map(|s| parse_port(s)).collect();11let all: Result<Vec<u16>, ParseError> = inputs.iter().map(|s| parse_port(s)).collect();The last line is the tell. collect can turn a collection of results into a result of a collection precisely because Result is data with a known shape, not a control-flow mechanism. No exception system can do that.
The struct-with-optional-fields anti-pattern
The reason sums matter in practice is that their absence has a standard workaround, and the workaround is where a specific class of production bug lives. Without sums, "one of several shapes" becomes a record containing all the fields any shape might need, each of them optional, plus a rule — written in a comment, a validator, or nobody's head — about which combinations are meaningful.
Every consumer of that record must now re-derive the rule. Most get it right; one checks data != null without checking error != null and renders a stale success view over a failed request. Nothing in the type system is capable of noticing, because the type genuinely permits that state. The type was asked whether the fields are the right *types*, and it answered correctly; it was never asked whether the combination was legal, because there was no way to ask.
The transformation to a sum is mechanical: identify the states, make each a variant, move the fields that only exist in that state into that variant. What you gain is that the excess states stop being representable. What you pay is a match at every consumer instead of a field access, and a serialization format that now has to carry a tag — which is a real cost at an API boundary, where a sum has to be encoded as an object with a type field and every client has to agree on the spelling.
That boundary cost is not a reason to avoid sums internally. It is a reason to do the conversion once, at the edge, in a parse step — which is the same conclusion [[gradual-typing]] and [[nullability]] arrive at from different directions, and which the Backend Engineering domain names parse-don't-validate.
type Req<T> = {
loading: boolean
data: T | null
error: Error | null
}
// representable states: 2 * (|T|+1) * 2type Req<T> =
| { kind: "loading" }
| { kind: "loaded"; data: T }
| { kind: "failed"; error: Error }
// representable states: 1 + |T| + |Error|The rewrite preserves behaviour only if the three variants genuinely partition the states the program can reach — that is, if no reachable state has both data and error set, and no reachable state has loading true together with either. Establish that by enumerating the writers of the record, not by reading the type: the type permitted the excess states, so the evidence has to come from the code that produced them.
Some producer really does set data and error together — a stale-while-revalidate cache that keeps the last good value alongside a refresh failure is the common real case. Then the domain has four states, not three, and the correct sum has four variants (including { kind: "stale"; data: T; error: Error }). Collapsing to three silently drops the stale value and users see a spinner where they had content.
How it works
The steps, in the order the compiler takes them.
- The declaration registers a closed set of variants in the symbol table; each variant is a constructor function from its payload types to the sum type.
- The checker lays the type out as a discriminant (tag) plus storage large enough for the largest payload, with alignment padding as required by the target.
- Construction writes the tag and the payload; there is no way to produce a value of the type without going through a constructor, which is what makes the tag trustworthy.
- A match reads the tag, branches, and binds the payload fields of the selected variant — see
[[pattern-matching]]for the surface and[[pattern-matching-compilation]]for the decision tree it becomes. - The exhaustiveness checker enumerates the declared variants, subtracts those covered by the arms, and reports a witness value if the remainder is non-empty.
- Where a variant is uninhabited or a payload occupies a value the tag could otherwise use, the layout algorithm may fold the tag into unused bit patterns of the payload — the niche optimization described in
[[nullability]].
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A record of optional fields reaches a state its comment said was impossible; a consumer that checked one field and not the other renders a success view over a failed request, and the report is "sometimes it shows stale data" with no reproduction.
- A sum is added to a public API and serialized without a tag, so clients discriminate by which fields are present; a later variant adds a field that overlaps and every client silently routes it to the wrong branch.
- A codebase adopts
Resultin a language with no propagation operator; call sites accumulate nested matches, someone introduces anunwrap-equivalent helper, and within a quarter the failure paths are unhandled again but now with more ceremony. - A recursive sum is defined without an indirection and the compiler reports an infinitely sized type — a confusing message whose actual meaning is that the layout algorithm cannot pick a size.
- A variant is added to an enum used across a module boundary and the build breaks in fifty files at once; the team adds a wildcard arm to each to get green, and the new variant is now silently unhandled everywhere.
When it helps
- Modelling anything with distinct states that carry different data: request lifecycles, parse results, protocol messages, UI modes, state machines.
- Any tree-shaped structure, especially an AST or an expression language, where recursion plus variants is the natural description.
- Error handling where you want the failure path to appear in the signature and to compose with ordinary data operations.
- Refactoring: when the cardinality of the model exceeds the cardinality of the domain, the sum is the mechanical fix and the compiler finds all the sites.
When it hurts
- At a serialization boundary, where the tag has to be spelled out in the wire format and every client must agree on it — a cost
[[type-erasure]]and API versioning both make worse. - In a language without exhaustiveness checking, where the closed-set guarantee is unenforced and the sum degrades to a tagged record with extra ceremony.
- When the variant set genuinely needs to be extended by third parties. Sums are closed by design; that is the wrong shape for a plugin interface, where an interface plus dynamic dispatch is right.
- For a type with one dominant variant and a rare one, where the match at every site costs more in noise than the excluded states cost in risk — though that judgement is wrong more often than people think.
What it costs
Every one of these is paid by something.
- Making illegal states unrepresentable buys the elimination of a whole class of state bugs and costs every consumer a match instead of a field access, plus a real conversion step at every boundary where the data arrives untagged.
- A closed variant set buys exhaustiveness checking and pays with versioning: adding a variant is a breaking change for every exhaustive consumer, which is exactly why
#[non_exhaustive]and its equivalents exist. - Tag-plus-payload layout costs memory — the type is as large as the biggest variant plus the tag and alignment — which matters for large collections of small values, and is why niche optimizations are worth implementing.
- Sums push the failure and absence paths into signatures, which buys reviewability and costs signature noise: a function that could fail says so everywhere it appears, including in the types of everything that calls it.
What else you could do
What a different compiler or language does instead, and when that is better.
- Subtype polymorphism with an abstract base and virtual dispatch: adding a case needs no change at any use site, but writing an operation that considers all cases in one place becomes impossible. This is the expression problem, and it is the exact dual of the sum-type trade.
- A record of optional fields with a validating constructor centralises the "which combinations are legal" rule in one place. Weaker than a sum — the type still admits the illegal states — but it is the pragmatic answer in a language without sums.
- Exceptions instead of
Result: the happy path stays uncluttered and the failure path is invisible in signatures. Better when failures are genuinely exceptional and every caller would only propagate; worse whenever a caller ought to be forced to decide. - An open enum with an integer or string tag, as in most wire formats, keeps forward compatibility with unknown variants at the cost of exhaustiveness — the right choice at a protocol boundary and the wrong one inside a module.
See it for yourself
The flag, dump or tool that shows you this directly.
rustc -Z print-type-sizes(nightly) prints the computed layout of every type, including which variant dominated the size and where padding went — the fastest way to see tag-plus-payload made concrete.cargo expandshows what?andderiveexpanded into, which turns the ergonomics ofResultback into the matches they desugar from.ghciwith:infoand:kindshows a Haskelldatadeclaration's constructors and arity;:set -ddump-simplshows the case expressions the compiler generated from them.- For TypeScript, hover a discriminated union and read the members; the cardinality argument is visible in the hover text once you start counting.
- For the cardinality claim itself, the reliable inspection is arithmetic on paper: count the states the type admits, count the states the domain has, and look at the difference.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Algebraic just means fancy enums." It means the type constructors form an algebra with addition and multiplication, and the arithmetic is a working tool for finding over-permissive data models, not a metaphor.
- "A sum type is a union type." A sum is closed, tagged and nominal — declared once, with constructors. A union is open, untagged and structural — composable anywhere. See
[[union-types]]for what falls out of that difference. - "
Resultis just a wrapper, exceptions do the same thing more conveniently." Exceptions are control flow and cannot be stored, collected, returned alongside a normal value, or transformed as data. That is the whole difference and it shows up the moment you want a list of results. - "Optional fields are the same thing with less ceremony." They admit combinations that the sum does not. The ceremony is the checking, and removing it is removing the guarantee.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
A product type holds several things at once — a struct, a record, a tuple. A sum type holds exactly one of several possibilities, and remembers which — an enum with payloads. Most languages have had products forever; sums are the ones that keep getting left out, and their absence is why so much code has a struct full of optional fields and a comment about which combinations are valid.
practical
The working technique is counting. Write down how many distinct states your type can represent and how many your domain actually has. If the model number is bigger, the difference is the set of states you are excluding by convention, and each one is a branch somebody will forget. Converting to a sum is mechanical: one variant per real state, and the fields that only exist in that state move inside it. The compiler will then walk you through every site that needs updating — which is the payoff, and also why you should do the conversion before the codebase is large rather than after.
advanced
The arithmetic keeps going, and the extensions are genuinely useful. Function types are exponentials: A -> B has |B|^|A| values, which is why currying (A, B) -> C into A -> B -> C is an isomorphism — (C^B)^A = C^(A×B). Generic containers are functors, and the recursive types you write are fixed points of polynomial functors, which is where the derivative-of-a-type trick comes from: differentiating a type gives you its zipper, the type of a one-hole context for navigating it. None of this is required to use sum types well, but it explains why the refactorings that feel mechanical really are mechanical — they are algebraic identities, and a compiler could in principle check them.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
enum layout unspecified without #[repr], and rustc already deviates from it via niche optimization, packing the discriminant into unused bit patterns of a payload where one exists. Haskell's GHC uses boxed constructors with an info pointer instead, so the memory story there is entirely different.switch faces. Whether any particular match becomes a table is a codegen decision you should verify in the disassembly rather than assume — see [[pattern-matching-compilation]].If you were asked this in an interview
- Explain why sum and product types are called "algebraic", using a concrete cardinality calculation.
- Here is a struct with
loading,dataanderrorfields. How many states does it represent, how many does the domain have, and what would you change? - What does a language give up by making a sum type's variant set closed, and what does it get?