Algebraic data types and state modeling

Overview

Algebraic data types combine structures that contain several values together with structures that choose one of several alternatives. The word algebraic reflects the way these combinations can be interpreted as products and sums.

A member record containing both a name and an email combines fields. A search result that is loading, ready, or failed has alternatives with different requirements: success needs results, while failure needs an error. Defining each alternative makes those relationships explicit in the type, instead of leaving every field optional in one object.

A type model selects the combinations that make sense for the application from all the values a program could construct. Consumers handle the fields belonging to each case. This is the basis of the familiar idea of making invalid states harder to represent.

Types describe data shapes and relationships. Whether an order was actually paid or a server is trustworthy requires runtime checks. Separating representation, transition rules, and validation of external input makes the type model's scope clear.

History

• 1969: Burstall's structural-induction research appeared.¹

• The 1970s: Robin Milner's ML began as a metalanguage for the LCF theorem prover at Edinburgh.¹

• 1977: Burstall introduced NPL and published program-transformation research with Darlington.¹

• 1980: Burstall, MacQueen, and Sannella introduced Hope in “HOPE: An Experimental Applicative Language” at the LISP Conference.²

• September 1987: A meeting at FPCA in Portland discussed a common language amid several non-strict, purely functional languages. This discussion led to Haskell.¹

• April 1, 1990: The first Haskell report appeared. Algebraic data declarations formed part of a language combining functions, type inference, and pattern matching.¹

• July 2010: The final Haskell 2010 report appeared, retaining constructor-and-field declarations in the official language definition.³⁴

• January 16, 2015: Microsoft announced TypeScript 1.4, which introduced union types.⁵

• September 2016: TypeScript 2.0 supported narrowing tagged unions through discriminant properties.⁶⁷

The lineages of type inference and data declarations

Type inference and data declarations came to work together in functional languages, but their starting points differ. ML strongly influenced polymorphic type inference, while the Haskell designers' 2007 history says that algebraic types were absent from original ML. That history identifies Burstall's NPL and Hope by Burstall, MacQueen, and Sannella as predecessors of algebraic types as a language feature, so ML's origins and the lineage of ADT declarations need to be read separately.¹

The history distinguishes original ML from its successor Standard ML, and also lists Miranda among earlier languages with algebraic types. Treating every version of a language family as one language hides these changes.¹

Constructors and case analysis

The lineage through NPL in 1977 and Hope in 1980 made data alternatives explicit in language declarations and used patterns to decompose values. The Haskell history places Burstall's structural-induction work and his program-transformation research with Darlington in the background of this programming style.¹

The Hope paper explains the motivation for defining the shapes of user-defined values through distinct constructors and handling each case. A tree might be empty, a tip containing a value, or a branch containing two subtrees. Paired declarations and case analysis let consumers follow the forms the data can take.²

Recursive declarations express lists or syntax trees; pattern matching selects a computation for each form.³ A result type can similarly attach a value to success and a reason to failure, making the relationship “success has a result” visible in the declaration instead of leaving it as an implicit agreement across the program.

Sums and products

Sum and product describe these relationships between values. Tagged alternatives form a sum; fields contained together in one alternative form a product. Two fields with two and three possible values yield 2×3=6 combinations. Tagged alternatives containing two possible values in one case and three in the other yield 2+3=5 cases.

According to the Haskell history, Haskell took Miranda's style of declaring algebraic types as a sum of products. Hope and Standard ML separate sums from tuple products: a tree branch can take two fields directly, or one tuple containing two subtrees, depending on the declaration style.¹

The relationship among possible values can be distinguished from the syntax declaring it. Haskell's notation is one way to express that relationship; different notation can express the same data construction.

Case analysis through unions and discriminants

TypeScript unions and discriminant properties look different from functional-language constructors, but address the related problem of declaring alternatives and handling their fields within object types. State models can give loading, success, and failure their required data instead of admitting accidental combinations of independent fields. A screen that retains old results while loading can explicitly model that combination too.

Type notation determines which values to represent. Functions and module boundaries express which events permit transitions between states.

The scope of a modern type model

A sum type describes the current shape of data, while parametric polymorphism lets a structure be reused across types. In Result<T, E>, the success/failure alternatives and reuse across T and E illustrate these separate roles.

TypeScript erases type annotations at runtime, so external JSON requires executable field checks. A type assertion creates no validator. Inside a program, never can check whether case analysis has left an alternative unhandled.⁸⁹

A discriminated-union state example

This example applies case analysis to a TypeScript search state. It expresses only the relationship that success has results and failure has an error; it does not implement a search API.

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'] }));

The output is Ada, Grace. The value { kind: 'ready' } produces a compile error because the required data field is missing. In the default branch, assigning to never produces an error when a new state is added without a matching case.