Variants, options and recursive types

List.nth [10; 20] 5 stops with Exception: Failure "nth", while List.nth_opt [10; 20] 5 returns None, a value the caller must handle before it can use the answer. Both rely on variant types, OCaml’s way of saying “one of these cases”, and the same idea describes trees and whole expressions.

You will define variants with and without data, use option where other languages use null, declare types that refer to themselves, and write functions with one case per constructor, which the compiler checks for you.

A variant lists the cases a value can be

A variant typevariant type: A type that lists every form its values can take, each a constructor, such as type shape = Circle of float | Dot. names every form a value may take. Each form is a constructorconstructor: A capitalised name such as Some or Circle that builds one case of a variant type, with or without values inside, and names that case in patterns., written with a capital letter: Dot carries nothing, Circle carries a float, and Rect carries an inline record with fields w and h. A match, or a function with one case per constructor, takes the value apart:

from session import toplevel, write

# A variant type lists its cases. A constructor may carry values, here a float or an inline record, or nothing. A match
# that leaves a constructor out draws warning 8 with an example, and a constructor is not a function.
write("shapes.ml", """type shape = Circle of float | Rect of { w : float; h : float } | Dot

let area = function
  | Circle r -> Float.pi *. r *. r
  | Rect { w; h } -> w *. h
  | Dot -> 0.
""")
toplevel("""
#use "shapes.ml";;
List.map area [Circle 1.; Rect { w = 2.; h = 3. }; Dot];;
List.map Circle [1.; 2.];;
List.map (fun r -> Circle r) [1.; 2.];;
type colour = Red | Green | Blue;;
let name = function Red -> "red" | Green -> "green";;
type t = A | B of int | C;;
compare C (B 0);;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# #use "shapes.ml";;
type shape = Circle of float | Rect of { w : float; h : float; } | Dot
val area : shape -> float = <fun>
# List.map area [Circle 1.; Rect { w = 2.; h = 3. }; Dot];;
- : float list = [3.14159265358979312; 6.; 0.]
# List.map Circle [1.; 2.];;
Line 1, characters 9-15:
1 | List.map Circle [1.; 2.];;
             ^^^^^^
Error: This expression should not be a constructor, the expected type is
       'a -> 'b
# List.map (fun r -> Circle r) [1.; 2.];;
- : shape list = [Circle 1.; Circle 2.]
# type colour = Red | Green | Blue;;
type colour = Red | Green | Blue
# let name = function Red -> "red" | Green -> "green";;
Line 1, characters 11-51:
1 | let name = function Red -> "red" | Green -> "green";;
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched: Blue

val name : colour -> string = <fun>
# type t = A | B of int | C;;
type t = A | B of int | C
# compare C (B 0);;
- : int = -1

area gave 3.14159265358979312 for Circle 1., 6. for the rectangle and 0. for Dot. Two details stand out. A constructor is not a function: List.map Circle [1.; 2.] was refused, “This expression should not be a constructor”, while fun r -> Circle r worked. And the compiler checks that every case is handled. name matched Red and Green but not Blue, and OCaml answered with “Warning 8 [partial-match]: this pattern-matching is not exhaustive”, followed by an example of a value that is not matched, Blue.

The last line is a trap for later. The built-in compare orders constructors without arguments before those with arguments, whatever the order of declaration: for type t = A | B of int | C, compare C (B 0) was -1. Write your own comparison when the order means something in your domain.

option makes a missing answer part of the type

There is no null in OCaml. A function that may have no answer returns an optionoption: The standard variant type 'a option = None | Some of 'a, used for a result that may be missing instead of a null value., which the standard library defines as an ordinary variant: #show_type option printed type 'a option = None | Some of 'a. The caller receives None or Some value and has to look:

from session import toplevel

# option is an ordinary variant of the standard library: None or Some value. A function that may have no answer returns
# one, and the caller must handle both cases; List.nth raises an exception where List.nth_opt returns None.
toplevel("""
#show_type option;;
List.nth [10; 20] 5;;
List.nth_opt [10; 20] 5;;
List.nth_opt [10; 20] 1;;
let safe_div a b = if b = 0 then None else Some (a / b);;
(safe_div 7 2, safe_div 7 0);;
let describe = function None -> "no answer" | Some q -> "quotient " ^ string_of_int q;;
describe (safe_div 7 0);;
Option.value ~default:0 (safe_div 7 0);;
Option.map (fun q -> q * 10) (safe_div 7 2);;
safe_div 7 2 + 1;;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# #show_type option;;
type 'a option = None | Some of 'a
# List.nth [10; 20] 5;;
Exception: Failure "nth".
# List.nth_opt [10; 20] 5;;
- : int option = None
# List.nth_opt [10; 20] 1;;
- : int option = Some 20
# let safe_div a b = if b = 0 then None else Some (a / b);;
val safe_div : int -> int -> int option = <fun>
# (safe_div 7 2, safe_div 7 0);;
- : int option * int option = (Some 3, None)
# let describe = function None -> "no answer" | Some q -> "quotient " ^ string_of_int q;;
val describe : int option -> string = <fun>
# describe (safe_div 7 0);;
- : string = "no answer"
# Option.value ~default:0 (safe_div 7 0);;
- : int = 0
# Option.map (fun q -> q * 10) (safe_div 7 2);;
- : int option = Some 30
# safe_div 7 2 + 1;;
Line 1, characters 0-12:
1 | safe_div 7 2 + 1;;
    ^^^^^^^^^^^^
Error: This expression has type int option
       but an expression was expected of type int

List.nth [10; 20] 5 raised Failure "nth", an exception the caller may forget to catch; List.nth_opt returned None for position 5 and Some 20 for position 1. safe_div 7 2 gave Some 3 and safe_div 7 0 gave None. The type does the reminding: safe_div 7 2 + 1 was refused, because an int option is not an int.

describe handled both cases with a match, Option.value ~default:0 turned None into 0, and Option.map applied a function inside: Some 3 became Some 30.

A type can refer to itself, and take a type parameter

A recursive typerecursive type: A type whose definition refers to itself, such as a tree whose Node constructor holds two smaller trees. mentions itself in one of its constructors. A binary tree is either empty, Leaf, or a Node holding a left tree, a value and a right tree; the parameter 'a lets the same type hold ints, strings or anything else, written 'a tree. Inserting 5, 3, 8 and 1 into a binary search tree keeps smaller values on the left. Step through the insertions:

The session builds the same tree with the type and its functions, then the tree a sorted input gives:

from session import toplevel, write

# A recursive, parameterised type: an 'a tree is a Leaf or a Node holding a left tree, a value and a right tree. Each
# function has one case per constructor and calls itself where the type refers to itself.
write("tree.ml", """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 size = function Leaf -> 0 | Node (l, _, r) -> size l + 1 + size r

let rec height = function Leaf -> 0 | Node (l, _, r) -> 1 + max (height l) (height r)
""")
toplevel("""
#use "tree.ml";;
let t = List.fold_left (fun t x -> insert x t) Leaf [5; 3; 8; 1];;
to_list t;;
(size t, height t);;
let sorted = List.fold_left (fun t x -> insert x t) Leaf [1; 2; 3; 4; 5];;
(size sorted, height sorted);;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# #use "tree.ml";;
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
val insert : 'a -> 'a tree -> 'a tree = <fun>
val to_list : 'a tree -> 'a list = <fun>
val size : 'a tree -> int = <fun>
val height : 'a tree -> int = <fun>
# let t = List.fold_left (fun t x -> insert x t) Leaf [5; 3; 8; 1];;
val t : int tree =
  Node (Node (Node (Leaf, 1, Leaf), 3, Leaf), 5, Node (Leaf, 8, Leaf))
# to_list t;;
- : int list = [1; 3; 5; 8]
# (size t, height t);;
- : int * int = (4, 3)
# let sorted = List.fold_left (fun t x -> insert x t) Leaf [1; 2; 3; 4; 5];;
val sorted : int tree =
  Node (Leaf, 1,
   Node (Leaf, 2, Node (Leaf, 3, Node (Leaf, 4, Node (Leaf, 5, Leaf)))))
# (size sorted, height sorted);;
- : int * int = (5, 5)

The toplevel printed the tree as nested constructors, Node (Node (Node (Leaf, 1, Leaf), 3, Leaf), 5, Node (Leaf, 8, Leaf)), with 5 at the root. to_list read it in order, [1; 3; 5; 8], and (size t, height t) was (4, 3). Inserting [1; 2; 3; 4; 5] in sorted order gave a tree of height 5 for 5 values: each node has only a right child, so the tree is a list in disguise and a search walks every node. Balanced trees, as in the standard library’s Set and Map, exist to prevent that.

Recursive functions follow the shape of their type

The functions on trees share a pattern: one case per constructor, and a recursive call wherever the constructor holds a value of the type itself. size returns 0 for Leaf and size l + 1 + size r for a Node; height does the same with max. An expression treeexpression tree: A tree that represents a formula, with numbers at the leaves and operators such as Add or Mul at the inner nodes, so that evaluating it is a recursive walk. shows the pattern again, with arithmetic: Num holds a number, and Add and Mul hold two sub-expressions each. Step through eval on Add (Num 2, Mul (Num 3, Num 4)):

from session import toplevel, write

# An expression tree: a syntax tree for arithmetic. eval and show follow the type, one case per constructor and one
# recursive call per sub-expression.
write("expr.ml", """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
""")
toplevel("""
#use "expr.ml";;
let e = Add (Num 2, Mul (Num 3, Num 4));;
(show e, eval e);;
let f = Mul (Add (Num 2, Num 3), Num 4);;
(show f, eval f);;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# #use "expr.ml";;
type expr = Num of int | Add of expr * expr | Mul of expr * expr
val eval : expr -> int = <fun>
val show : expr -> string = <fun>
# let e = Add (Num 2, Mul (Num 3, Num 4));;
val e : expr = Add (Num 2, Mul (Num 3, Num 4))
# (show e, eval e);;
- : string * int = ("(2 + 3 * 4)", 14)
# let f = Mul (Add (Num 2, Num 3), Num 4);;
val f : expr = Mul (Add (Num 2, Num 3), Num 4)
# (show f, eval f);;
- : string * int = ("(2 + 3) * 4", 20)

eval e gave 14 and show e printed (2 + 3 * 4); the second tree, Mul (Add (Num 2, Num 3), Num 4), printed as (2 + 3) * 4 and gave 20. The shape of the data decided the order of the work: Mul sits above Add in the second tree, so the addition happens first. Because each function has a case for every constructor, adding a new one, say Sub, makes the compiler point to every function that does not handle it yet, through warning 8.

Practise: variants, options and trees

The questions use the session’s shapes, options, trees and expressions with new values. Work out each result before you check:

Interview questions

Warm-up (fresher to 2–5 years): what is option in OCaml, and why is it used instead of null?

option is a variant type from the standard library, type 'a option = None | Some of 'a. A function that may have no result returns None in that case and Some value otherwise, as List.nth_opt does. Because int option is a different type from int, the caller cannot use the result as a number until it has handled both cases, with a match or helpers such as Option.value ~default. A null in other languages hides inside every value and fails at run time; an option puts the possibility of “no answer” in the type, where the compiler can check it.

Two harder questions follow, about a match that started failing after a new case was added and about a tree that became slow. Decide what you would check first, then open each first step:

Key takeaways

• A variant type lists every case as a constructor; constructors may carry values, are not functions, and a match that misses one draws warning 8 with an example.
• option, None or Some v, puts a missing answer in the type, so the caller handles it with a match, Option.value or Option.map before using the value.
• A recursive, parameterised type such as 'a tree refers to itself in its constructors, and a sorted input gives a search tree as deep as a list.
• A function that follows its type has one case per constructor and one recursive call per sub-value of the type, so the compiler can point to any case a new constructor leaves out.