OCaml has a concise and expressive system for creating new data
types. Pattern matching provides a natural way to inspect and
deconstruct values of those types.
Variants
Variant types
Variants represent data that can be in one of a fixed number of
forms. We will use a small colour type to see why this works so
well with pattern matching:
Variant types
type colour =
| Red
| Green
| Blue
let red = Red
A variant value is in exactly one of a fixed set of forms.
Each form is named by a constructor, which must start with a capital
letter; lowercase is a syntax error, not merely a style convention.
The type lists every constructor, which is what lets the
compiler check a match for completeness.
A variant is closest to a Rust enum or a Java sealed hierarchy.
type colour =
| Red
| Green
| Blue
let red = Red
Records
Record types
Records in OCaml represent a collection of named elements. A
simple example is a point record containing x, y and z
fields:
Record types
type point = {
x : int;
y : int;
z : int;
}
A record groups a fixed set of named fields.
Each field is declared with its own type.
The field names are part of the type, so point is distinct
from any other record with three int fields.
It resembles a Rust/C struct, Python dataclass or Java record,
and is immutable unless a field is explicitly marked mutable.
type point = {
x : int;
y : int;
z : int;
}
We can create instances of our point type using { ... }, and
access the elements of a point using the '.' operator:
Creating and accessing records
let origin = { x = 0; y = 0; z = 0 }
let get_y r = r.y
let o = get_y origin
Records represent a collection of named elements.
Create instances using { ... }.
Access elements using the . operator.
Functional update
New records can also be created from existing records using the
with keyword. For example, we can create a new point which is
the same as origin except with the value of its z field
changed to 10:
Functional update
let p = { origin with z = 10 }
New records can be created from existing records using the
with keyword.
The new record is the same as origin except the z field is
changed to 10.
Field punning
Another useful trick with records is field punning, which allows
you to replace:
Field punning
let mk_point x y z = { x; y; z }
When a variable has the same name as the field, write the name
once instead of { x = x; y = y; z = z }.
The same shorthand works in patterns when matching a record.
let mk_point x y z = { x = x; y = y; z = z }
with
let mk_point x y z = { x; y; z }
Tuples
A tuple groups a fixed number of values without naming the fields. Its type
uses *, and its value and pattern use commas. Tuples are useful for small,
local combinations such as a pair of counters; use a record when field names
would make the meaning clearer.
Tuples
let score = (3, 2)
let describe_score (x, o) =
Printf.sprintf "X: %d, O: %d" x o
let x_score = fst score
score has type int * int.
(x, o) destructures the pair and names both components.
This is like a tuple in Python or Rust; fst and snd work on pairs.
Write shift : point -> int * int -> point which moves a point by
the given pair of offsets in the x and y directions, leaving
its z field untouched.
let shift p (dx, dy) = failwith "not implemented"let check b m = if not b then failwith m
let () =
check
(shift { x = 0; y = 0; z = 0 } (2, 3) = { x = 2; y = 3; z = 0 })
"shift the origin";
check
(shift { x = 1; y = 1; z = 5 } (-1, 4) = { x = 0; y = 5; z = 5 })
"shift leaves z alone";
check
(shift { x = 7; y = 8; z = 9 } (0, 0) = { x = 7; y = 8; z = 9 })
"shift by (0, 0)";
print_endline "all tests passed"
Show reference solution
Only x and y change, so this is what functional update is for:
{ p with ... } carries z over unchanged. The pair of offsets is
taken apart by the parameter pattern (dx, dy), so there is no
need for fst and snd.
let shift p (dx, dy) = { p with x = p.x + dx; y = p.y + dy }
Variants with data
Constructor arguments
Variant constructors can also have arguments. This allows variants
to contain different types of data depending on which constructor
was used. For example, we can create a type which contains either
a point or a colour:
Constructor arguments
type t =
| Point of point
| Colour of colour
let p_or_c cond pnt col = if cond then Point pnt else Colour col
let p = p_or_c true origin red
Variant constructors can have arguments.
This allows a variant to contain different types of data
depending on which constructor was used.
Multiple constructor arguments
Variant constructors can contain multiple arguments separated by
the * symbol:
Multiple constructor arguments
type drawing =
| Triangle of point * point * point
| Gradient of colour * colour
let bg = Gradient (Red, Green)
A Triangle carries its three corners; a Gradient carries the
two colours it fades between.
Separate several arguments with * in the declaration.
Building such a constructor needs parentheses around the
arguments.
type drawing =
| Triangle of point * point * point
| Gradient of colour * colour
Creating these constructors with multiple arguments requires
parentheses:
let bg = Gradient (Red, Green)
Pattern matching
Before we go on, let us define a small helper that prints a string
to the terminal.
let show s = print_endline s
Now we can print a message:
show "Hello, world!"
Inspecting variants
So far we have created some values of variant types, but how do we
get the data back out of them? The answer is pattern matching.
Using a match expression we can deconstruct a variant value and
retrieve its constructor's arguments:
Inspecting variants
let show s = print_endline s
let print_t t =
match t with
| Point p -> show (Printf.sprintf "Point: %d %d %d" p.x p.y p.z)
| Colour c -> show (Printf.sprintf "Colour")
match takes a value apart by asking which constructor built
it.
Point p is a pattern, not an expression: it binds a fresh p
to the constructor's argument.
That p shadows any existing p for the length of the branch.
let print_t t =
match t with
| Point p -> show (Printf.sprintf "Point: %d %d %d" p.x p.y p.z)
| Colour c -> show (Printf.sprintf "Colour")
let () = print_t (Point { x = 5; y = 9; z = 0 })
let () = print_t (Colour Blue)
Here Point p and Colour c are not expressions but patterns.
They describe the shape of the data and bind variables to
different parts of it. Note that the p in Point p does not
refer to an existing p variable, instead it is creating a new
p variable bound to the argument of the Point constructor.
Nested patterns
We can nest patterns within other patterns to do pattern matching
on the constructor arguments. For example, we can print the names
of the different colours in our print_t function:
Nested patterns
let print_t t =
match t with
| Point p -> show (Printf.sprintf "Point: %d %d %d" p.x p.y p.z)
| Colour Red -> show (Printf.sprintf "Red")
| Colour Green -> show (Printf.sprintf "Green")
| Colour Blue -> show (Printf.sprintf "Blue")
A pattern can contain further patterns, matching a constructor
and its argument in one step.
Colour Red matches only the Colour case whose payload is
Red.
let print_t t =
match t with
| Point p -> show (Printf.sprintf "Point: %d %d %d" p.x p.y p.z)
| Colour Red -> show (Printf.sprintf "Red")
| Colour Green -> show (Printf.sprintf "Green")
| Colour Blue -> show (Printf.sprintf "Blue")
let () = print_t (Colour Red)
let () = print_t (Colour Blue)
Exhaustiveness
A key feature of pattern matching, which can help prevent many
errors especially when refactoring, is that the compiler will warn
you if you forget to handle a particular case. For example, if we
had forgotten the Colour Green case in the above definition:
Exhaustiveness
let print_t_ t =
match t with
| Point p -> show (Printf.sprintf "Point: %d %d %d" p.x p.y p.z)
| Colour Red -> show (Printf.sprintf "Red")
| Colour Blue -> show (Printf.sprintf "Blue")
Lines 2-5, characters 5-50:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched: Colour Green
The compiler knows every constructor, so it can tell when a
match misses one.
It names an unmatched example, here Colour Green.
This is what makes adding a constructor safe: every incomplete
match is reported.
let print_t_ t =
match t with
| Point p -> show (Printf.sprintf "Point: %d %d %d" p.x p.y p.z)
| Colour Red -> show (Printf.sprintf "Red")
| Colour Blue -> show (Printf.sprintf "Blue")
Lines 2-5, characters 5-50:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched: Colour Green
Pattern guards
A branch may add a boolean condition with when. The branch is selected only
when both its pattern and its guard match. Guards are useful when the shape of
the data is not enough by itself:
Pattern guards
let sign n =
match n with
| n when n < 0 -> "negative"
| 0 -> "zero"
| _ -> "positive"
when n < 0 is a guard on the first pattern.
Guards are tested from top to bottom, like the surrounding branches.
Keep the fallback branch: guards do not make a match exhaustive.
Matching records
We can also match on record data using the same syntax as to
create records, including field punning. So our print_t can be
further refined to:
Matching records
let print_t t =
match t with
| Point { x; y; z } -> show (Printf.sprintf "Point: %d %d %d" x y z)
| Colour Red -> show (Printf.sprintf "Red")
| Colour Green -> show (Printf.sprintf "Green")
| Colour Blue -> show (Printf.sprintf "Blue")
Records are matched with the same { ... } syntax used to
build them.
Field punning works here too: { x; y; z } binds three
variables named after the fields.
let print_t t =
match t with
| Point { x; y; z } -> show (Printf.sprintf "Point: %d %d %d" x y z)
| Colour Red -> show (Printf.sprintf "Red")
| Colour Green -> show (Printf.sprintf "Green")
| Colour Blue -> show (Printf.sprintf "Blue")
The _ pattern
Sometimes, you do not care about a value. In that case you can use
the _ pattern, which matches any value without binding it to a
name:
The _ pattern
let is_colour_red t =
match t with
| Colour Red -> true
| _ -> false
Sometimes you do not care about a matched value.
The _ pattern matches any value without binding it to a name.
Match ordering
Note that patterns are matched from top to bottom: if a value
matches multiple patterns then the first of those patterns will be
selected. For example, in the following code the second case will
never be matched:
Match ordering
let is_colour_red t =
match t with
| _ -> false
| Colour Red -> true
Line 4, characters 7-17:
Warning 11 [redundant-case]: this match case is unused.
Patterns are tried top to bottom, and the first match wins.
A catch-all _ placed first makes every later case dead, and
the compiler says so.
let is_colour_red t =
match t with
| _ -> false
| Colour Red -> true
Line 4, characters 7-17:
Warning 11 [redundant-case]: this match case is unused.
Suppose print_t_ (defined earlier) omits the Colour Green case
of the t variant. What does OCaml do?
Nothing: OCaml has no way to know a case is missing.
It raises a runtime exception the first time Colour Green
is matched.
The compiler emits a "this pattern-matching is not
exhaustive" warning at compile time, naming Colour Green
as an example of an unmatched value.
It silently falls through to the Point case.
Why: the compiler knows every constructor of t and colour
from their type definitions, so it can check a match against
the full set of shapes a value could take. A missing case is
flagged statically, before the program ever runs, which is one of
pattern matching's main safety benefits over an if/else chain
on manually-extracted fields.
Parameterised types
Types in OCaml can be parameterised by other types. For example,
the option type which may or may not contain a value:
Parameterised types
type 'a option =
| None
| Some of 'a
let io = Some 6
let co = Some Green
'a is a type variable, standing for any type.
Supplying it gives a concrete type: int option,
colour option, and so on.
One definition serves every element type.
Use an option where many languages might use null: None means
“no value”, while Some x carries a value. None is not a universal null;
it belongs only to an option type.
type 'a option =
| None
| Some of 'a
In the above the 'a is a type variable, which can be
substituted by any type. For instance, we can create a value of
type int option or a value of type colour option:
let io = Some 6
let co = Some Green
We can define a printer for t option type as follows:
let print_t_opt t =
match t with
| None -> show "None"
| Some t -> print_t tlet () = print_t_opt (Some (Colour Red))
let () = print_t_opt None
Polymorphic values
These type variables also appear when creating polymorphic
values. For example, the following function has type
'a option -> 'a list which means it can be applied to any
option type:
Polymorphic values
let opt_to_list o =
match o with
| Some x -> [x]
| None -> []
opt_to_list has type 'a option -> 'a list.
It never inspects the element, so it works for every 'a.
One definition applies to int option, colour option and
the rest.
let opt_to_list o =
match o with
| Some x -> [x]
| None -> []
let l = opt_to_list (Some 9)
let m = opt_to_list (Some Red)
Polymorphic constructors
Constructors of parameterised types which do not include the type
parameter, such as None in the optional type, are also examples
of polymorphic values:
Polymorphic constructors
let n = None
let a = [ Some 3; n ]
let b = [ n; Some Blue ]
None mentions no 'a, so it has type 'a option and fits
any element type.
The same n is usable in an int option list and in a
colour option list.
let n = None
let a = [ Some 3; n ]
let b = [ n; Some Blue ]
Recursive data types
Data types in OCaml can also be recursive. This allows us to
create recursive structures such as trees and lists. The following
defines a parametric binary tree type:
Recursive data types
type 'a binary_tree =
| Leaf
| Tree of 'a binary_tree * 'a * 'a binary_tree
Data types in OCaml can be recursive.
This allows creating recursive structures such as trees and
lists.
As you can see the Tree constructor of binary_tree contains
other binary_trees as its arguments.
Inspecting recursive data types
We can write recursive functions to handle these recursive data
types. For example, the following function returns the maximum
depth of a binary tree:
Inspecting recursive data types
let rec depth tr =
match tr with
| Leaf -> 1
| Tree(left, _, right) ->
1 + (max (depth left) (depth right))
A recursive type is consumed by a recursive function.
The pattern has one branch per constructor: Leaf stops the
recursion, Tree recurses into both subtrees.
Computing a tree's depth
let n4 = Tree (Leaf, 4, Leaf)
let n2 = Tree (Leaf, 2, n4)
let n3 = Tree (Leaf, 3, Leaf)
let tree = Tree (n2, 1, n3)
let d = depth tree
Leaf returns 1, so a leaf counts as a level of its own.
The highlighted path 1 -> 2 -> 4 -> Leaf is the longest in this
tree: four levels, so d is 4.
let rec depth tr =
match tr with
| Leaf -> 1
| Tree(left, _, right) ->
1 + (max (depth left) (depth right))
let tree : int binary_tree =
Tree(Tree(Leaf,
2,
Tree(Leaf,
4,
Leaf)),
1,
Tree(Leaf,
3,
Leaf))
let d = depth tree
Lists
Constructing lists
A particularly common built-in data type in OCaml is the list
type. list is actually a parameterised recursive variant type.
It has two constructors :: (called cons) and [] (called nil).
[] represents an empty list and :: adds an element to the
front of the list:
Constructing lists
let l = 1 :: 2 :: 3 :: []
let nil = []
let l = 1 :: 2 :: 3 :: nil
list is a parameterised recursive variant type with two
constructors, :: (cons) and [] (nil).
[] represents an empty list; :: adds an element to the front
of the list.
OCaml also provides a shorthand syntax for lists: [ ..; .. ].
Our l value above could instead have been defined:
let l = [1; 2; 3]
Matching lists
Like all constructors, the list constructors can be used as
patterns in pattern matching. The following function sums all the
elements of an int list:
Matching lists
let rec sum il =
match il with
| [] -> 0 (* empty list *)
| i :: rest -> i + (sum rest)
[] and :: are ordinary constructors, so they work as
patterns.
i :: rest splits a list into its head and its tail.
The empty-list case is what ends the recursion.
let rec sum il =
match il with
| [] -> 0 (* empty list *)
| i :: rest -> (* head + sum of tail *) i + (sum rest)
let s = sum l
Write min_list : int list -> int option to compute the minimum
element of an integer list. Return None for the empty list, and
Some e when the minimum element is e.
let rec min_list_helper cur_min l =
match l with
| [] -> cur_min
| x :: xs ->
(match cur_min with
| None -> failwith "not implemented"
| Some m -> failwith "not implemented")
let min_list l = min_list_helper None llet check b m = if not b then failwith m
let () =
check (min_list [] = None) "min_list []";
check (min_list [3; 1; 2] = Some 1) "min_list [3;1;2]";
check (min_list [5] = Some 5) "min_list [5]";
print_endline "all tests passed"
Show reference solution
The helper's None branch should start the running minimum at
x; the Some m branch should keep whichever of m and x is
smaller.
let rec min_list_helper cur_min l =
match l with
| [] -> cur_min
| x :: xs ->
(match cur_min with
| None -> min_list_helper (Some x) xs
| Some m -> min_list_helper (Some (min m x)) xs)
let min_list l = min_list_helper None l
Write postfix : 'a binary_tree -> 'a list that returns the
elements of a binary tree in postfix order (left subtree, then
right subtree, then the node itself). Use the list append operator
@.
let rec postfix t = failwith "not implemented"let check b m = if not b then failwith m
let () =
check (postfix Leaf = []) "postfix Leaf";
check
(postfix
(Tree
( Tree (Leaf, 0, Leaf),
1,
Tree (Tree (Leaf, 5, Leaf), 4, Leaf) ))
= [0; 5; 4; 1])
"postfix example tree";
print_endline "all tests passed"
Show reference solutionlet rec postfix t =
match t with
| Leaf -> []
| Tree (left, v, right) -> postfix left @ postfix right @ [v]
Write rev_list : 'a list -> 'a list that reverses a list. Use the
list append operator @ (an O(n) accumulator-based version is a
nice follow-up once you've seen this one work).
let rec rev_list l = failwith "not implemented"let check b m = if not b then failwith m
let () =
check (rev_list [] = []) "rev_list []";
check (rev_list [1; 2; 3] = [3; 2; 1]) "rev_list [1;2;3]";
check (rev_list [1] = [1]) "rev_list [1]";
print_endline "all tests passed"
Show reference solutionlet rec rev_list l =
match l with
| [] -> []
| x :: xs -> rev_list xs @ [x]
Optional: mutation and references
Most of the workshop uses immutable values. OCaml also supports
mutation when changing state in place is the clearer tool.
Optional: mutation
type mpoint = { mutable x : int; mutable y : int; mutable z : int }
let p = { x = 0; y = 0; z = 10 }
let () = p.z <- 20
A field must be declared mutable before it can be assigned.
<- updates the existing record; { p with z = 20 } instead
makes a new record.
Reference cells provide one mutable value without defining a new
record type:
Optional: references
let counter = ref 0
let () = counter := !counter + 1
let seen = !counter
ref v creates a mutable cell holding v.
Read it with ! and update it with :=.
A reference is a record with one mutable field.
Optional: type aliases
An alias gives an existing type another name. It does not create a
distinct type:
Optional: type aliases
type int_pair = int * int
let id (x : int_pair) = x
type NAME = ... gives an existing type a second name.