Algebraic data types and state modeling
Trace algebraic data types from NPL and Hope through Haskell to TypeScript, with sums, products, and a state-modeling example.
· Last updated: 2026-11-07 · 8 min read
Overview
Algebraic data types (ADTs) build data definitions out of two operations: product types that bundle several fields together, and sum types that pick exactly one branch out of several mutually exclusive alternatives. Why “algebraic”? Because the total number of distinct values you can construct follows ordinary multiplication and addition.
A member record holding both a name and an email is a product of two fields. A search screen that is currently loading, ready, or failed is a sum whose branches need different payloads: ready needs a result list, whereas failed needs an error reason, and declaring each branch as its own alternative bakes those requirements straight into the type instead of leaving every field optional on one baggy object.
State modeling is the art of carving the combinations that actually mean something to the domain out of all the raw bit patterns a program could assemble. Downstream code then handles each branch's guaranteed fields directly, which is the concrete mechanism behind the slogan “make invalid states unrepresentable.”
Types still have borders. A type declaration fixes data shapes in memory, not whether an invoice was genuinely paid or whether a remote JSON payload can be trusted; keeping static representation, state-transition functions, and runtime boundary validation distinct makes the type model's job crystal clear.
History
1969: Burstall's structural-induction research appeared.1
The 1970s: Robin Milner's ML began as a metalanguage for the LCF theorem prover at Edinburgh.1
1977: Burstall introduced NPL and published program-transformation research with Darlington.1
1980: Burstall, MacQueen, and Sannella introduced Hope in “HOPE: An Experimental Applicative Language” at the LISP Conference.2
September 1987: A meeting at FPCA in Portland discussed a common language amid several non-strict, purely functional languages. This discussion led to Haskell.1
April 1, 1990: The first Haskell report appeared. Algebraic data declarations formed part of a language combining functions, type inference, and pattern matching.1
July 2010: The final Haskell 2010 report appeared, retaining constructor-and-field declarations in the official language definition.34
January 16, 2015: Microsoft announced TypeScript 1.4, which introduced union types.5
September 2016: TypeScript 2.0 supported narrowing tagged unions through discriminant properties.67
The lineages of type inference and data declarations
Polymorphic type inference and algebraic data declarations feel inseparable in modern functional languages, yet they grew out of different roots. As the Haskell designers noted in their 2007 history paper, Robin Milner's original ML pioneered polymorphic type inference without having algebraic data types at all; explicit data-variant declarations entered the lineage through Rod Burstall's NPL (1977) and Hope by Burstall, MacQueen, and Sannella (1980), so the history of ML inference and the history of ADT declarations have to be traced separately.1
That same historical account separates original Edinburgh ML from its successor Standard ML and credits Miranda as an early bearer of algebraic types. Flattening forty years of ML-family languages into a single name erases when and where these features actually met.1
Constructors and case analysis
What NPL (1977) and Hope (1980) brought to the table was declaring all legal constructors of a type up front and tearing values back apart by pattern matching. The Haskell history traces the roots of that style to Burstall's 1969 work on structural induction and his program-transformation papers with John Darlington.1
Read the 1980 Hope paper and the motivation is immediate: a binary tree is either empty, a leaf tip holding one value, or a branch holding two subtrees, and pairing those named constructors with case analysis lets every function that consumes a tree mirror the exact shapes the data can take.2
Self-referential declarations build recursive structures like lists or abstract syntax trees, while pattern matching dispatches the right calculation for each constructor.3 Likewise, a Result type attaches a payload only to its success constructor and an error reason only to its failure constructor, turning “success carries data” from a scattered gentleman's agreement into a rule enforced at declaration time.
Sums and products
Sums and products count possibilities differently. Pair a two-value field with a three-value field in one record (a product) and you get combinations; split them into two tagged branches where one branch holds two possible values and the other holds three (a sum) and you get cases.
According to the Haskell history, Haskell borrowed Miranda's habit of writing an algebraic type directly as a sum of products. Compare that with Hope and Standard ML, where sum constructors and tuple products are separate notions, so a tree branch either takes two fields directly or takes a single 2-tuple holding the two subtrees depending on the language's declaration style.1
The combinatorial relationship among values is one thing; the surface syntax a language chooses to spell it is another. Haskell's data keyword is one notation, not the only one.
Case analysis through unions and discriminants
TypeScript's union types (|) and discriminant properties look nothing like ML or Haskell constructors on the surface, yet they solve the exact same problem inside structural object types. Instead of scattering isLoading, data, and error as independent optional fields that can accidentally all be true or null at once, a discriminated union gives loading, success, and failure their exact required fields, and if a screen genuinely needs to keep showing stale results while refreshing in the background, you model that state as its own explicit variant.
Type declarations fix which snapshots of state can exist. Functions and module boundaries decide which events may move the system from one state to another.
The scope of a modern type model
Notice too how sum types and parametric polymorphism divide the work: in Result<T, E>, the sum structure splits success from failure, while type parameters T and E let that two-branch shape be reused across any payload and error types.
Because TypeScript erases all type annotations before execution, untrusted JSON crossing a network boundary still needs an executable validator (as checks nothing at runtime), whereas once validated data is inside the program, assigning the leftover variable in a default branch to never lets the compiler flag any newly added union variant you forgot to handle.89
A discriminated-union state example
The TypeScript snippet below models a search view as a discriminated union so the compiler demands data on the ready branch and error on the error branch.
type Search =
| { kind: 'loading' }
| { kind: 'ready'; data: string[] }
| { kind: 'failed'; error: string };
function describe(state: Search): string {
switch (state.kind) {
case 'loading': return 'Loading';
case 'ready': return state.data.join(', ');
case 'failed': return state.error;
default: {
const impossible: never = state;
return impossible;
}
}
}
console.log(describe({ kind: 'ready', data: ['Ada', 'Grace'] }));
Running it prints Ada, Grace. Writing { kind: 'ready' } without data fails to compile, and adding a fourth variant to SearchState without updating the switch triggers a compile-time error on the never assignment in default.
See also
Footnotes
- Paul Hudak, John Hughes, Simon Peyton Jones, and Philip Wadler, “A History of Haskell: Being Lazy With Class,” HOPL III, 2007, introduction and §5–5.1. A designers' history of NPL, Hope, original ML, Miranda, and Haskell. Paper. ↩
- R. M. Burstall, D. B. MacQueen, and D. T. Sannella, “HOPE: An Experimental Applicative Language,” LISP Conference, 1980, §2–3.1. Author-hosted paper. ↩
- Haskell 2010 Language Report, §4.2.1 “Algebraic Datatype Declarations.” Official report. ↩
- Simon Marlow, “ANNOUNCE: Haskell 2010 Report (final),” Haskell mailing list, 2010-07-06. Announcement. ↩
- Microsoft, “Announcing TypeScript 1.4,” 2015-01-16. Announcement. ↩
- Microsoft, TypeScript 2.0, 2016, “Tagged union types.” Release notes. ↩
- Microsoft, “TypeScript 2.0 is now available!”, TypeScript blog, 2016-09-22. Announcement. ↩
- TypeScript Handbook, “Type Assertions.” Official documentation. ↩
- TypeScript Handbook, “Exhaustiveness checking.” Official documentation. ↩