Skip to content
LumenaryAcademy
Foundations 55 min

Records and variants

Design types that say exactly what your data can be, and let the compiler check every function that uses them.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

Types as a design tool

Most bugs in data-heavy programs come from data in a state that should not exist: an order marked "shipped" with no shipping date, a payment that is both "card" and "cash", a parcel that is "waiting at the depot" and also "signed for by M. Rossi". In many languages the type system cannot help, because the data is a class with a status string and a handful of fields that may or may not be set.

OCaml gives you two kinds of type to build with. A record groups several named values that belong together (this and that). A variant lists the alternatives a value may be (this or that), each with exactly the data that belongs to it. Combined, they let you write types in which the impossible states cannot even be constructed. Then pattern matching, with the exhaustiveness check you met in the previous lesson, makes sure every function handles every real case. Experienced OCaml programmers spend a good share of their design time on these types, because once they are right, much of the code almost writes itself.

DefinitionsH

Records and variants

Definition— Record

type book = { title : string; year : int } declares a record type. A value is built with { title = "Ficciones"; year = 1944 }, a field is read with b.title, and { b with year = 1956 } builds a copy with some fields replaced. Fields are immutable unless declared mutable (lesson 6).

Definition— Variant

type shape = Circle of float | Rectangle of float * float declares a variant type with two constructors. Constructor names start with a capital letter. A constructor may carry nothing (Waiting), one value, a tuple of values, or an inline record (Triangle of { a : float; b : float; c : float }). Values are built by applying constructors and taken apart by pattern matching.

Definition— Recursive and parameterised types

A type may refer to itself (type expr = Num of int | Add of expr * expr) and may take type parameters, written before its name: type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree. The standard 'a list, 'a option and ('a, 'e) result are exactly such types.

Definition— Polymorphic variant

A constructor written with a backquote, such as `Red, is a polymorphic variant. It needs no type declaration, and the same constructor can belong to several types. They are useful for flexible interfaces in libraries; ordinary variants are the default choice.

Worked examplesH

Records, variants and trees

Records

ocaml
(* A record type: named fields, all immutable by default. *)
type book = { title : string; author : string; year : int; copies : int }

let catalogue =
  [
    { title = "Things Fall Apart"; author = "Chinua Achebe"; year = 1958; copies = 2 };
    { title = "Ficciones"; author = "Jorge Luis Borges"; year = 1944; copies = 0 };
  ]

(* Field punning: { title; author; _ } binds variables named after the fields. *)
let describe { title; author; year; _ } = Printf.sprintf "%s by %s (%d)" title author year

let find wanted = List.find_opt (fun b -> b.title = wanted) catalogue

(* { b with ... } builds a copy with some fields changed. *)
let borrow b =
  if b.copies <= 0 then Error ("no copies of " ^ b.title ^ " are left")
  else Ok { b with copies = b.copies - 1 }

let check_out wanted =
  match find wanted with
  | None -> wanted ^ ": not in the catalogue"
  | Some book -> (
      match borrow book with
      | Error reason -> wanted ^ ": sorry, " ^ reason
      | Ok updated -> Printf.sprintf "%s: borrowed, %d left" wanted updated.copies)

let () =
  List.iter (fun b -> print_endline (describe b)) catalogue;
  List.iter (fun t -> print_endline (check_out t)) [ "Things Fall Apart"; "Ficciones"; "Dune" ];
  Printf.printf "oldest: %d\n" (List.fold_left (fun acc b -> min acc b.year) max_int catalogue)
text
Things Fall Apart by Chinua Achebe (1958)
Ficciones by Jorge Luis Borges (1944)
Things Fall Apart: borrowed, 1 left
Ficciones: sorry, no copies of Ficciones are left
Dune: not in the catalogue
oldest: 1944

Notice that we never wrote the type book when building values or reading fields: OCaml infers the record type from the field names. That is convenient, but it means two record types in the same scope should not share field names, or the most recently defined one wins and you may need an annotation. (Putting each type in its own module, as lesson 5 shows, is the usual solution.)

In a pattern, { title; author; year; _ } is shorthand for { title = title; author = author; year = year; _ }: it binds variables named after the fields, and _ says "and I am deliberately ignoring the other fields". The record update { b with copies = ... } builds a new record; the catalogue is untouched. The nested match in check_out is wrapped in parentheses, a rule worth memorising: an inner match inside a branch must be parenthesised, or its cases swallow the outer match's remaining cases.

Variants

ocaml
(* A variant type: a shape is one of three things, each with its own data. *)
type shape =
  | Circle of float
  | Rectangle of float * float
  | Triangle of { a : float; b : float; c : float } (* an inline record *)

let area = function
  | Circle r -> Float.pi *. r *. r
  | Rectangle (w, h) -> w *. h
  | Triangle { a; b; c } ->
      let s = (a +. b +. c) /. 2. in
      sqrt (s *. (s -. a) *. (s -. b) *. (s -. c))

let name = function
  | Circle _ -> "circle"
  | Rectangle (w, h) when w = h -> "square"
  | Rectangle _ -> "rectangle"
  | Triangle _ -> "triangle"

(* Make illegal states unrepresentable: each state carries exactly its own data. *)
type parcel =
  | Waiting
  | In_transit of { driver : string }
  | Delivered of { day : string; signed_by : string option }

let status = function
  | Waiting -> "waiting at the depot"
  | In_transit { driver } -> "on its way with " ^ driver
  | Delivered { day; signed_by = Some who } -> Printf.sprintf "delivered on %s, signed by %s" day who
  | Delivered { day; signed_by = None } -> Printf.sprintf "delivered on %s, left at the door" day

let () =
  List.iter
    (fun s -> Printf.printf "%s: %.2f\n" (name s) (area s))
    [ Circle 1.; Rectangle (3., 4.); Rectangle (2., 2.); Triangle { a = 3.; b = 4.; c = 5. } ];
  List.iter
    (fun p -> print_endline (status p))
    [
      Waiting;
      In_transit { driver = "Thandiwe" };
      Delivered { day = "Tuesday"; signed_by = Some "M. Rossi" };
      Delivered { day = "Friday"; signed_by = None };
    ]
text
circle: 3.14
rectangle: 12.00
square: 4.00
triangle: 6.00
waiting at the depot
on its way with Thandiwe
delivered on Tuesday, signed by M. Rossi
delivered on Friday, left at the door

The parcel type is the heart of this lesson. A waiting parcel has no driver and no delivery day, an in-transit parcel has a driver, and a delivered one has a day and, optionally, a signature. There is no way to build a waiting parcel that was signed for. Every function that handles parcels matches on the constructor and receives exactly the fields that exist in that state.

Patterns can reach inside inline records and options at once: Delivered { day; signed_by = Some who } matches only delivered parcels that were signed, binding both the day and the name. And guards still work: Rectangle (w, h) when w = h picks out squares before the general rectangle case.

Now suppose that next year the business adds a state, Returned of { reason : string }. You add one line to the type, and the compiler immediately reports every match on parcels that does not handle it: status here, and every other function in a large codebase. That is why experienced OCaml programmers avoid the catch-all _ case on their own variant types: it would silently swallow the new constructor instead of letting the compiler point it out.

Recursive and parameterised types

ocaml
(* Recursive variants: an arithmetic expression is a number or an operation on expressions. *)
type expr =
  | Num of int
  | Add of expr * expr
  | Mul of expr * expr
  | Neg of expr

let rec eval = function
  | Num n -> n
  | Add (a, b) -> eval a + eval b
  | Mul (a, b) -> eval a * eval b
  | Neg e -> -eval e

let rec to_string = function
  | Num n -> string_of_int n
  | Add (a, b) -> "(" ^ to_string a ^ " + " ^ to_string b ^ ")"
  | Mul (a, b) -> to_string a ^ " * " ^ to_string b
  | Neg e -> "-" ^ to_string e

(* A parameterised type: a binary search tree holding values of any type 'a. *)
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, v, r) as t ->
      if x < v then Node (insert x l, v, r) else if x > v then Node (l, v, insert x r) else t

let rec to_list = function
  | Leaf -> []
  | Node (l, v, r) -> to_list l @ [ v ] @ to_list r

let rec depth = function
  | Leaf -> 0
  | Node (l, _, r) -> 1 + max (depth l) (depth r)

let () =
  let e = Mul (Add (Num 2, Num 3), Neg (Num 4)) in
  Printf.printf "%s = %d\n" (to_string e) (eval e);
  let t = List.fold_left (fun t x -> insert x t) Leaf [ 50; 30; 70; 20; 40; 60; 80; 30 ] in
  print_endline (String.concat " " (List.map string_of_int (to_list t)));
  let w = List.fold_left (fun t x -> insert x t) Leaf (String.split_on_char ' ' "the cat sat on the mat") in
  Printf.printf "%s (depth %d)\n" (String.concat " " (to_list w)) (depth w)
text
(2 + 3) * -4 = -20
20 30 40 50 60 70 80
cat mat on sat the (depth 5)

The expr type is a miniature of what compilers do all day. An expression is a tree, and every function over it (evaluate, print, simplify, type-check, compile) is a recursive function with one case per constructor. It is no accident that OCaml is a favourite language for writing compilers, and the project in lesson 9 grows this idea into a small language.

'a tree works for any element type that can be compared: the same insert builds a tree of ints and a tree of strings. It uses OCaml's built-in polymorphic comparison <, which is convenient; lesson 5 shows the more disciplined approach of passing in a comparison function through a module. The pattern Node (l, v, r) as t names the whole matched value t while also taking it apart, so an already-present element returns the existing tree unchanged.

As with lists, nothing is mutated: inserting builds a new path from the root to the new node and shares all the untouched subtrees with the old tree.

IntuitionH

Counting values, and polymorphic variants

Why "sum" and "product" types? Count the values. A record { ready : bool; urgent : bool } has 2 × 2 = 4 possible values: a product. The variant Waiting | In_transit of bool has 1 + 2 = 3: a sum. When you design a type, compare the number of values it allows with the number of situations that really exist. Every extra value is a state your code must defend against; a well-designed variant has none to spare.

How are these values stored? Cheaply. A constructor without arguments, such as Waiting or Leaf, is represented as a small integer, just like an int; a constructor with arguments is a single heap block whose header records which constructor it is, followed by its fields. Matching on a variant is therefore a quick test of that tag, compiled to a jump table when there are many constructors, not a chain of string comparisons. Records are blocks too, with fields in declaration order. Knowing this explains why idiomatic OCaml can use variants everywhere without worrying about speed.

Polymorphic variants relax one rule: their constructors, written with a backquote, do not belong to a single declared type. The toplevel shows how their types are inferred:

text
# let describe_colour = function
  | `Red -> "red"
  | `Green -> "green"
  | `Rgb (r, g, b) -> Printf.sprintf "#%02x%02x%02x" r g b;;
val describe_colour : [< `Green | `Red | `Rgb of int * int * int ] -> string =
  <fun>
# describe_colour (`Rgb (255, 128, 0));;
- : string = "#ff8000"

The type [< `Green | `Red | `Rgb of int * int * int ] reads "any polymorphic variant using at most these constructors". Different functions can accept overlapping sets, and libraries use this for options and error types that should combine freely. The price is longer types and less helpful error messages, so most application code sticks to ordinary variants.

ExplanationH

Designing types the way professionals do

Experienced OCaml programmers often design the types of a feature before writing any functions, and talk about them in code review as much as about the code. Some habits worth adopting early:

Parse, don't re-check. Convert raw input (strings from a form, rows from a file) into precise types once, at the edge of the program, and return a result if that fails. Inside the program, functions then receive values that are valid by construction: a parcel that is Delivered always has a day. Compare that with passing raw strings around and re-validating them in every function.

Give each concept its own type, even when the representation is the same. A customer identifier and an order identifier may both be strings, but type customer_id = Customer_id of string and type order_id = Order_id of string cannot be mixed up. (Lesson 5 shows how a module with an abstract type does this even more firmly, at no run-time cost.)

Prefer variants to booleans and strings for states. paid : bool; refunded : bool has four combinations, one of them (refunded but never paid) meaningless. type payment_state = Unpaid | Paid of date | Refunded of { paid : date; refunded : date } has exactly the three real ones.

Let option say "maybe", and only where it is true. A record whose every field is an option is usually a sign that it describes several different situations, each of which deserves its own constructor.

Generate the boilerplate. Printing, comparing and serialising records and variants by hand is tedious and error-prone. Projects add a line such as [@@deriving show, eq, yojson] after a type declaration and let ppx_deriving or ppx_yojson_conv write those functions; you will see these attributes everywhere in industrial code.

OCaml has more advanced tools in the same spirit, which you will meet in libraries rather than write on day one: private types (type t = private int), whose values can be read like the underlying type but only created by the defining module; and GADTs (generalised algebraic data types), variants whose constructors can refine the type parameter, used for typed interpreters, protocols and, as lesson 8 shows, effects.

Common misconceptionsH

Common misconceptions

Misconception

"I can change a record's field with r.x <- 3.." Only if the field was declared mutable. Otherwise the compiler stops you: Error: The record field x is not mutable. Build an updated copy with { r with x = 3. }; it is cheap, because the other fields are shared, not copied deeply.

Misconception

"A catch-all | _ -> makes a match safer." On your own variant types it does the opposite: it hides new constructors from the exhaustiveness check. Prefer listing every constructor, so that adding one produces a warning at every place that needs attention.

Misconception

"Variants are just enums." Enums in C or Java (before recent versions) are lists of names. OCaml variants carry data, differ in shape from constructor to constructor, can be recursive and parameterised, and are checked by pattern matching. Rust's enum, Swift's enum with associated values and Kotlin's sealed classes are the closest relatives.

Misconception

"Constructors are functions, so I can pass Some to List.map." In OCaml they are not first-class: List.map Some [1; 2] is rejected with "This expression should not be a constructor". Write List.map (fun x -> Some x) [1; 2], or use a helper such as Option.some. (Haskell, by contrast, does treat constructors as functions.)

Misconception

"Polymorphic variants are the modern, better variants." They solve specific problems (open, combinable sets of constructors), at the cost of more complicated types. Use ordinary variants unless you need what polymorphic ones offer.

Exercises

Exercises

1. Records and variants

Warm-upComputational

What does this program print?

type point = { x : int; y : int }

let () =
  let p = { x = 1; y = 2 } in
  let q = { p with y = 5 } in
  Printf.printf "%d %d\n" (q.x + p.y) q.y

2. Records and variants

CoreHuman

How many different values does this type have?

type t = A | B of bool | C of bool * bool

3. Records and variants

CoreHuman

A payment is made in cash, by card (with the last four digits), or by mobile money (with a phone number). Which type models it best?

Choose one

4. Records and variants

CoreComputational

What does this program print?

type expr = Num of int | Add of expr * expr | Mul of expr * expr

let rec eval = function
  | Num n -> n
  | Add (a, b) -> eval a + eval b
  | Mul (a, b) -> eval a * eval b

let rec show = function
  | Num n -> string_of_int n
  | Add (a, b) -> "(" ^ show a ^ " + " ^ show b ^ ")"
  | Mul (a, b) -> show a ^ " * " ^ show b

let () =
  let e = Mul (Add (Num 1, Num 2), Add (Num 3, Num 4)) in
  Printf.printf "%s = %d\n" (show e) (eval e)

5. Records and variants

CoreHuman

Your team's style guide says: on your own variant types, list every constructor instead of ending a match with | _ -> .... Why?

Choose one

6. Records and variants

CoreComputational

What does this program print?

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, v, r) as t ->
      if x < v then Node (insert x l, v, r)
      else if x > v then Node (l, v, insert x r)
      else t

let rec depth = function
  | Leaf -> 0
  | Node (l, _, r) -> 1 + max (depth l) (depth r)

let () =
  let t = List.fold_left (fun t x -> insert x t) Leaf [ 3; 1; 2; 5; 4 ] in
  Printf.printf "%d\n" (depth t)

7. Records and variants

Warm-upComputational

With type point = { x : float; y : float } and let p = { x = 1.; y = 2. }, the line p.x <- 3. is rejected. How do you get a point like p but with x equal to 3?

Choose one

Further reading and resources