Skip to content
LumenaryAcademy
Foundations 55 min

Lists, pattern matching, options and results

The everyday immutable list, taken apart with match; the List module's toolkit; and option and result, OCaml's honest answers to "maybe nothing" and "maybe an error".

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

The workhorse and its two companions

The list is OCaml's everyday collection: an immutable, singly linked sequence of values of one type. It is to OCaml what the array is to C or the list to Python, with two differences that shape how you use it. It never changes (adding an element at the front creates a new list that shares the old one), and you take it apart by pattern matching: "if it is empty, do this; if it has a first element and a rest, do that".

This lesson also introduces two small types from the standard library that you will use in nearly every function you write. option says there may be no value: the result of looking something up, parsing a number, finding the first match. result says this may fail, and here is why. Both replace the null references and many of the exceptions of other languages, and because they are ordinary types, the compiler checks that you handled every case.

DefinitionsH

Lists, matches, options, results

Definition— List

A value of type 'a list is either the empty list [] or x :: rest, an element x of type 'a in front of a list rest. [1; 2; 3] is shorthand for 1 :: 2 :: 3 :: []. xs @ ys appends two lists, copying xs.

Definition— match and function

match e with | p1 -> e1 | p2 -> e2 compares e with each pattern in order and evaluates the branch of the first that matches. function | p1 -> e1 | ... is shorthand for fun x -> match x with | p1 -> e1 | .... A pattern may have a guard, | p when condition -> e, which must also hold.

Definition— Exhaustiveness

The compiler checks that every possible value matches some pattern. If not, it emits warning 8 with an example of an unmatched value; at run time an unmatched value raises the exception Match_failure. Projects built with dune treat many warnings, including this one, as errors in development builds.

Definition— option

type 'a option = None | Some of 'a. A function that may have no answer returns an option, and the caller must match on it, or use helpers such as Option.value ~default, Option.map and Option.bind.

Definition— result

type ('a, 'e) result = Ok of 'a | Error of 'e. A function that may fail returns Ok value or Error explanation, where the explanation can be a string or, better, a variant type describing what went wrong.

Worked examplesH

Lists in practice

Pattern matching on lists

ocaml
(* Recursive functions over lists, by pattern matching. *)
let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let rec join_names = function
  | [] -> "nobody"
  | [ a ] -> a
  | [ a; b ] -> a ^ " and " ^ b
  | a :: rest -> a ^ ", " ^ join_names rest

(* Patterns can be nested, and a guard (when ...) adds a condition. *)
let describe = function
  | [] -> "empty"
  | [ _ ] -> "a single element"
  | x :: y :: _ when x = y -> "starts with a repeat"
  | x :: _ -> Printf.sprintf "starts with %d" x

let () =
  let xs = [ 3; 1; 4; 1; 5; 9; 2; 6 ] in
  Printf.printf "sum %d, length %d\n" (sum xs) (List.length xs);
  print_endline (join_names [ "Ana"; "Kofi"; "Mei"; "Ravi" ]);
  List.iter (fun l -> print_endline (describe l)) [ []; [ 7 ]; [ 2; 2; 3 ]; [ 1; 2 ] ];
  let ys = 0 :: xs in
  (* :: adds at the front in constant time; xs itself is unchanged and shared *)
  Printf.printf "%d %d %d\n" (List.length xs) (List.length ys) (List.length (xs @ ys))
text
sum 31, length 8
Ana, Kofi, Mei and Ravi
empty
a single element
starts with a repeat
starts with 1
8 9 17

Each function's cases follow the shapes a list can have. sum has the two essential ones: empty, and an element followed by the rest. join_names adds patterns for lists of exactly one and exactly two elements; order matters, because the first matching case wins, so the general a :: rest comes last. describe uses a nested pattern, x :: y :: _, matching lists of at least two elements, and a guard that tests whether the first two are equal. _ matches anything without naming it.

0 :: xs builds a new list in constant time whose tail is xs: nothing is copied, and xs still has eight elements. That sharing is safe precisely because lists never change. xs @ ys, on the other hand, must copy all of xs, so it costs time proportional to the length of its left argument.

Leave out a case and the compiler tells you. A real toplevel session:

text
# let first = function x :: _ -> x;;
Line 1, characters 12-32:
1 | let first = function x :: _ -> x;;
                ^^^^^^^^^^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched: []

val first : 'a list -> 'a = <fun>
# first [];;
Exception: Match_failure ("//toplevel//", 1, 12).

The warning names the forgotten case, [], before the program ever runs. Treat it as an error: either handle the case or change the type so that it cannot occur.

The List module

ocaml
let () =
  let temps = [ 21; 24; 19; 30; 28; 17; 25 ] in
  let days = [ "Mon"; "Tue"; "Wed"; "Thu"; "Fri"; "Sat"; "Sun" ] in
  let show_ints l = "[" ^ String.concat "; " (List.map string_of_int l) ^ "]" in
  print_endline (show_ints (List.filter (fun t -> t >= 25) temps));
  print_endline (show_ints (List.sort compare temps));
  Printf.printf "total %d, max %d\n" (List.fold_left ( + ) 0 temps) (List.fold_left max min_int temps);
  let pairs = List.combine days temps in
  Printf.printf "Friday: %d\n" (List.assoc "Fri" pairs);
  let hot, mild = List.partition (fun (_, t) -> t >= 25) pairs in
  Printf.printf "hot: %s; mild: %d days\n" (String.concat " " (List.map fst hot)) (List.length mild);
  Printf.printf "%b %b %b\n" (List.mem 30 temps) (List.exists (fun t -> t < 18) temps)
    (List.for_all (fun t -> t > 10) temps);
  print_endline (show_ints (List.init 6 (fun i -> i * i)));
  print_endline (show_ints (List.concat_map (fun x -> [ x; x * 10 ]) [ 1; 2; 3 ]));
  (* fold_right builds from the right; fold_left accumulates from the left *)
  print_endline (List.fold_right (fun x acc -> string_of_int x ^ "," ^ acc) [ 1; 2; 3 ] "end");
  print_endline (List.fold_left (fun acc x -> "(" ^ acc ^ "-" ^ string_of_int x ^ ")") "0" [ 1; 2; 3 ])
text
[30; 28; 25]
[17; 19; 21; 24; 25; 28; 30]
total 164, max 30
Friday: 28
hot: Thu Fri Sun; mild: 4 days
true true true
[0; 1; 4; 9; 16; 25]
[1; 10; 2; 20; 3; 30]
1,2,3,end
(((0-1)-2)-3)

OCaml has no generic "print any value" function in compiled programs (the toplevel can show values because it knows their types at that moment), so the program builds its own show_ints. Libraries and the ppx_deriving preprocessor can generate printers for your types; for now, small helpers like this are normal.

The rest is the toolkit you will reach for daily:

  • List.filter, List.map and List.sort compare do what their names say. compare is the built-in structural ordering, so the same call sorts strings, tuples or lists.
  • List.fold_left f init xs runs through the list from the left with an accumulator; it is how you write sums, maxima and most "loops that build one value". List.fold_right combines from the right, as the last two lines make visible.
  • List.combine zips two lists into pairs, List.assoc looks up a key in a list of pairs (raising Not_found if absent; List.assoc_opt returns an option), and List.partition splits a list by a test. The pattern let hot, mild = ... takes the resulting pair apart.
  • List.mem, List.exists and List.for_all answer yes-or-no questions; List.init builds a list from its indices; List.concat_map maps and flattens.

A note on stack depth. A function like sum above is not tail-recursive: each call waits for the next. On a list of millions of elements it can overflow the stack. The standard library marks which functions are not tail-recursive: List.fold_right is one of them, while List.fold_left is tail-recursive, and since OCaml 5.1 so are List.map and List.append (@), thanks to an optimisation called tail-recursion modulo cons. When in doubt with long lists, prefer fold_left.

Options and results

ocaml
(* option: a value that may be missing. *)
let safe_div a b = if b = 0 then None else Some (a / b)

let show_opt = function
  | None -> "None"
  | Some n -> Printf.sprintf "Some %d" n

(* result: success with a value, or failure with an explanation. *)
let parse_age s =
  match int_of_string_opt (String.trim s) with
  | None -> Error ("not a number: " ^ s)
  | Some n when n < 0 -> Error (Printf.sprintf "negative age: %d" n)
  | Some n -> Ok n

(* let* chains results: stop at the first Error. *)
let ( let* ) = Result.bind

let parse_person line =
  match String.split_on_char ',' line with
  | [ name; age ] ->
      let* age = parse_age age in
      if String.trim name = "" then Error "empty name" else Ok (String.trim name, age)
  | _ -> Error ("expected name,age in " ^ line)

let () =
  print_endline (show_opt (safe_div 20 4) ^ " " ^ show_opt (safe_div 1 0));
  print_endline (show_opt (Option.map (fun x -> x * 10) (safe_div 20 4)));
  Printf.printf "%d %d\n" (Option.value ~default:0 (safe_div 1 0))
    (Option.value ~default:0 (List.find_opt (fun x -> x > 3) [ 1; 5; 9 ]));
  List.filter_map int_of_string_opt [ "12"; "x"; "7"; ""; "40" ]
  |> List.fold_left ( + ) 0
  |> Printf.printf "sum of the valid numbers: %d\n";
  List.iter
    (fun line ->
      match parse_person line with
      | Ok (name, age) -> Printf.printf "ok: %s is %d\n" name age
      | Error msg -> Printf.printf "error: %s\n" msg)
    [ "Zainab, 34"; "Lars,-2"; "Mia,abc"; " ,20"; "nofields" ]
text
Some 5 None
Some 50
0 5
sum of the valid numbers: 59
ok: Zainab is 34
error: negative age: -2
error: not a number: abc
error: empty name
error: expected name,age in nofields

The standard library follows a naming convention: functions that may fail come in pairs, such as int_of_string (which raises an exception on bad input) and int_of_string_opt (which returns an option); List.find and List.find_opt; List.assoc and List.assoc_opt. In modern code, prefer the _opt versions unless failure is truly exceptional.

Option.map applies a function inside a Some and leaves None alone. Option.value ~default supplies a fallback. List.filter_map applies a function returning an option and keeps only the Some results, the idiomatic way to "parse what you can".

let* is a binding operator, available since OCaml 4.08. Defining let ( let* ) = Result.bind makes let* age = parse_age age in rest mean: if parse_age age is Ok a, continue with rest where age is a; if it is an Error, the whole expression is that error. Without it, every step would need its own nested match. You can define let* for Option.bind in the same way, usually inside a small module so the two do not clash; libraries often provide such modules ready-made.

IntuitionH

Folds, and why match beats if

List.fold_left f init [a; b; c] computes f (f (f init a) b) c: start with init, and fold each element into the accumulator. It is the functional version of the loop

text
acc := init
for each x in list: acc := f acc x
return acc

and nearly every loop that builds a single value (a sum, a maximum, a count, a map from keys to totals) is a fold_left. List.fold_right f [a; b; c] init computes f a (f b (f c init)), which preserves the list's order when you build a new list and is the natural fold for structural recursion, at the cost of stack depth.

Why do OCaml programmers match on lists instead of testing if xs = [] then ... else List.hd xs ...? Because the pattern does two jobs at once: it tests the shape and names the parts, so you can never use the head of an empty list by mistake. And the exhaustiveness check covers you when the type changes. List.hd and List.tl exist, but they raise exceptions on empty lists, and experienced programmers rarely use them.

ExplanationH

Lists and errors in professional code

Lists are the default collection in OCaml, but not the only one, and experienced programmers switch structures when the access pattern demands it:

You needUseWhy
To build, filter and transform sequences, mostly front to backlistCheap ::, pattern matching, the whole List module
Fast access by index, or a fixed-size tablearray (lesson 6)Constant-time a.(i)
Lookup by keyMap (lesson 5) or Hashtbl (lesson 6)Logarithmic or constant time instead of the linear List.assoc
A possibly huge or infinite stream, produced on demandSeq (lesson 7)Elements computed only when consumed

List.assoc on a short list of pairs is perfectly fine; on ten thousand pairs searched in a loop, it is the bug.

For errors, the strings used in this lesson are a starting point. In larger programs, the error side of a result is usually a variant type of its own:

ocaml
type parse_error =
  | Not_a_number of string
  | Negative of int
  | Missing_field of string

A caller can then match on the specific error, decide which ones to recover from, and produce a message in one place; tests can check for Error (Negative (-2)) rather than for the exact wording of a sentence. When errors from several modules must be combined, some libraries use polymorphic variants (lesson 4) for error types, so that a function's error type can be the union of the errors of the functions it calls.

Finally, when you process many inputs, decide deliberately what one failure means. List.filter_map with an option silently skips bad items; a fold that stops at the first Error rejects the whole batch; collecting the errors in a list and reporting all of them at the end is often the friendliest choice for people fixing a data file.

Common misconceptionsH

Common misconceptions

Misconception

"[1, 2, 3] is a list of three numbers." In OCaml, the comma builds a tuple, so [1, 2, 3] is a list containing one element, the triple (1, 2, 3); the toplevel answers (int * int * int) list. List elements are separated by semicolons: [1; 2; 3].

Misconception

"Appending with @ is as cheap as adding with ::." x :: xs takes constant time. xs @ [x] copies all of xs, so building a list by appending one element at a time costs time proportional to n². Build with :: and call List.rev once at the end, or use List.map and friends.

Misconception

"List.fold_left and List.fold_right take their arguments in the same order." They do not: List.fold_left f init xs puts the initial value before the list, while List.fold_right f xs init puts it after, matching the direction in which each one combines. The function arguments differ too: fold_left's function receives (acc, x), fold_right's receives (x, acc). The types make mistakes compile-time errors, but it is worth memorising.

Misconception

"List.sort sorts my list." It returns a new, sorted list and leaves the original untouched, as every list function does. Only array functions such as Array.sort work in place.

Misconception

"None is OCaml's null." A string option and a string are different types; you cannot pass the option where a string is expected without first handling None. Ordinary values in OCaml are never null.

Misconception

"Results are just exceptions with extra typing." A result is an ordinary value: you can store it, put it in a list, map over it, and the function's type tells every caller that failure is possible. Exceptions (lesson 6) remain useful for truly exceptional situations and for exiting deep recursion quickly; the OCaml community generally uses result for errors a caller is expected to handle.

Exercises

Exercises

1. Lists, pattern matching, options and results

Warm-upHuman

What is the type of [1, 2, 3] in OCaml?

Choose one

2. Lists, pattern matching, options and results

CoreComputational

What does this program print?

let () = Printf.printf "%d\n" (List.fold_right (fun x acc -> x - acc) [ 10; 20; 30 ] 0)

3. Lists, pattern matching, options and results

CoreComputational

What does this program print?

let classify = function
  | [] -> "none"
  | [ x ] when x > 0 -> "one positive"
  | [ _ ] -> "one"
  | x :: _ :: _ when x mod 2 = 0 -> "many, even first"
  | _ -> "many"

let () =
  print_endline
    (String.concat " / " (List.map classify [ [ -3 ]; [ 4; 1 ]; [ 5 ]; [ 3; 3; 3 ] ]))

4. Lists, pattern matching, options and results

Warm-upComputational

What does this program print?

let () =
  let prices = [ ("tea", 3); ("coffee", 4) ] in
  let price item = Option.value ~default:(-1) (List.assoc_opt item prices) in
  Printf.printf "%d %d\n" (price "coffee") (price "juice")

5. Lists, pattern matching, options and results

StretchComputational

What does this program print?

let () =
  [ "3"; "three"; "30"; "0x10" ]
  |> List.filter_map int_of_string_opt
  |> List.fold_left ( + ) 0
  |> Printf.printf "%d\n"

6. Lists, pattern matching, options and results

CoreHuman

Which operation takes constant time, whatever the length of the list xs?

Choose one

7. Lists, pattern matching, options and results

CoreComputational

What does this program print?

let ( let* ) = Result.bind
let check n = if n > 100 then Error (Printf.sprintf "too big: %d" n) else Ok n

let () =
  let r =
    let* a = check 40 in
    let* b = check (a * 3) in
    let* c = check (b - 50) in
    Ok (a + c)
  in
  match r with
  | Ok v -> Printf.printf "ok %d\n" v
  | Error e -> print_endline e

Further reading and resources