Algebraic Data Types

Algebraic data types are the fundamental building blocks of programs in ML-style languages like Haskell and OCaml. Since they play such an important role in these languages, it is well worth understanding how they work and where they come from—at first, the design may feel a bit arbitrary, but in reality it flows naturally from a reasonable starting point.

Algebraic data types are made up of two components: products (also known as structs, records or tuples) and variants (also known as tagged unions, sums or coproducts). Let’s take a look at each of these in turn, how they can be combined and how they’re related.


Products are a construct that appears in most programming languages: it’s a type that contains multiple values. The simplest example in OCaml would be a pair (just like an ordered pair in mathematics):

# let pair = (1, 2);;
val pair : int * int = (1, 2)

This pair has the type int * int which means it has two members, both integers. In prose rather than code, this is often written as int × int because it corresponds to a cross-product of sets. Fundamentally, we can do two interesting things with a pair: get the first element or get the second element:

# let first (x, y) = x;;
val first : 'a * 'b -> 'a = <fun>
# let second (x, y) = y;;
val second : 'a * 'b -> 'b = <fun>

In OCaml, pattern matching makes the definitions pretty visual. The functions first and second are often abbreviated as fst and snd or π₁ and π₂ (π is used because these are projection functions).

Continue reading