Pattern matching in depth

A match on an integer with the cases 0, n when n > 0 and n when n < 0 covers every number, yet OCaml warns that it is not exhaustive and offers 1 as a value it may miss. The checker reads patterns, not guards, and knowing what it reads is the difference between a warning you can fix and one you learn to ignore.

You will combine or-patterns, as-patterns and guards, rewrite guarded matches so the checker can prove them complete, read warnings 8, 11 and 4, and handle an exception from the value being matched without hiding others.

Or-patterns, as-patterns and guards combine in one case

A pattern can do more than name a constructor. An or-patternor-pattern: A pattern p1 | p2 that matches when either side matches; both sides must bind the same variables., p1 | p2, matches when either side does, so (0, _) | (_, 0) catches a zero in either place. An as-pattern, p as name, matches p and also binds the whole matched value to name. A guardguard: A condition after a pattern, written when expr, that is tested only once the pattern has matched; if it is false, matching goes on to the next case., when condition, adds a test that runs only after the pattern has matched. Cases are tried from the top, and the first one whose pattern and guard both succeed wins. Step through the session’s classify on two of its inputs:

from session import toplevel, write

# Or-patterns, as-patterns and guards combine in one match. Cases are tried from the top; a guard (when …) is tested
# only after its pattern has matched. function is fun plus match on the argument.
write("classify.ml", """let classify = function
  | (0, _) | (_, 0) -> "has a zero"
  | (a, b) as p when a = b -> Printf.sprintf "(%d, %d) is a double" (fst p) (snd p)
  | (a, b) when a > 0 && b > 0 -> "both positive"
  | _ -> "other"

let first_two = function
  | x :: (y :: _ as rest) -> Printf.sprintf "%d then %d; tail %s" x y (String.concat "," (List.map string_of_int rest))
  | [x] -> Printf.sprintf "only %d" x
  | [] -> "empty"
""")
toplevel("""
#use "classify.ml";;
List.map classify [(0, 5); (4, 4); (2, 9); (-1, 3)];;
List.map first_two [[7; 8; 9]; [7]; []];;
""")

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

# #use "classify.ml";;
val classify : int * int -> string = <fun>
val first_two : int list -> string = <fun>
# List.map classify [(0, 5); (4, 4); (2, 9); (-1, 3)];;
- : string list =
["has a zero"; "(4, 4) is a double"; "both positive"; "other"]
# List.map first_two [[7; 8; 9]; [7]; []];;
- : string list = ["7 then 8; tail 8,9"; "only 7"; "empty"]

classify returned "has a zero" for (0, 5), "(4, 4) is a double" for (4, 4), "both positive" for (2, 9) and "other" for (-1, 3). Patterns also nest: in first_two, x :: (y :: _ as rest) takes the first element as x and binds the rest of the list, which must start with some y, to rest; for [7; 8; 9] it printed 7 then 8; tail 8,9. Both functions are written with function, which is fun x -> match x with in one word: the cases match the function’s single argument.

Guards are invisible to the exhaustiveness check

The compiler proves a match complete from its patterns alone. A guard is an arbitrary expression, so the checker treats every guarded case as one that may fail, and a match whose guards happen to cover everything still looks incomplete to it:

from session import toplevel

# Guards are not used by the exhaustiveness check, so a match whose guards cover every int still draws warning 8.
# Warning 11 marks a case that can never be reached. A refutation case, -> ., states that a case is impossible.
toplevel("""
let sign n = match n with 0 -> "zero" | n when n > 0 -> "positive" | n when n < 0 -> "negative";;
let sign n = match n with 0 -> "zero" | n when n > 0 -> "positive" | _ -> "negative";;
List.map sign [0; 12; -3];;
let f x = match x with _ -> 0 | 1 -> 1;;
let g = function Some 0 -> "zero" | Some _ -> "some" | None -> "none" | Some 1 -> "one";;
type empty = |;;
let only_none (x : empty option) = match x with None -> 0 | Some _ -> .;;
""")

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

# let sign n = match n with 0 -> "zero" | n when n > 0 -> "positive" | n when n < 0 -> "negative";;
Line 1, characters 13-95:
1 | let sign n = match n with 0 -> "zero" | n when n > 0 -> "positive" | n when n < 0 -> "negative";;
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched:
    1
    (However, some guarded clause may match this value.)

val sign : int -> string = <fun>
# let sign n = match n with 0 -> "zero" | n when n > 0 -> "positive" | _ -> "negative";;
val sign : int -> string = <fun>
# List.map sign [0; 12; -3];;
- : string list = ["zero"; "positive"; "negative"]
# let f x = match x with _ -> 0 | 1 -> 1;;
Line 1, characters 32-33:
1 | let f x = match x with _ -> 0 | 1 -> 1;;
                                    ^
Warning 11 [redundant-case]: this match case is unused.

val f : int -> int = <fun>
# let g = function Some 0 -> "zero" | Some _ -> "some" | None -> "none" | Some 1 -> "one";;
Line 1, characters 72-78:
1 | let g = function Some 0 -> "zero" | Some _ -> "some" | None -> "none" | Some 1 -> "one";;
                                                                            ^^^^^^
Warning 11 [redundant-case]: this match case is unused.

val g : int option -> string = <fun>
# type empty = |;;
type empty = |
# let only_none (x : empty option) = match x with None -> 0 | Some _ -> .;;
val only_none : empty option -> int = <fun>

The first sign drew “Warning 8 [partial-match]”, with 1 as an example of an unmatched value and the note “(However, some guarded clause may match this value.)”. The note is the compiler admitting that a guard might cover it, which it cannot check. The fix is to make the last case unguarded: in the second sign, _ -> "negative" handles whatever the guards did not, and the warning disappeared; List.map sign [0; 12; -3] gave ["zero"; "positive"; "negative"].

The same session shows two more messages. match x with _ -> 0 | 1 -> 1 drew “Warning 11 [redundant-case]: this match case is unused”: _ already took every value, so the case after it can never run. In g, Some 1 came after Some _, which had already matched it. The last line uses a refutation case, Some _ -> ., for a type with no values, empty: it tells the checker that a case is impossible, and the checker agreed. The manual’s chapter on GADTs is where this becomes common.

Warnings 8, 11 and 4 each point at a different fragility

Warning 8 means a value can reach no case and would raise Match_failure. Warning 11 means a case can never be reached, usually because a broader case above it already matches. A third warning protects against the future. A catch-all _ keeps a match exhaustive whatever happens to its type, so when the type gains a constructor the compiler has nothing to say. The session adds Pending to a status type and compiles twice:

from session import run, write

# A catch-all case keeps a match exhaustive when the type gains a constructor, so the compiler stays silent. Warning 4
# (fragile-match), off by default, reports such matches.
write("status.ml", """type status = Active | Suspended | Closed | Pending

let label = function
  | Active -> "active"
  | _ -> "inactive"

let can_log_in = function
  | Active -> true
  | Suspended | Closed -> false
""")
run("""
ocamlopt -c status.ml
ocamlopt -w +4 -c status.ml
""")

$ ocamlopt -c status.ml
File "status.ml", lines 7-9, characters 17-31:
7 | .................function
8 |   | Active -> true
9 |   | Suspended | Closed -> false
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched: Pending
$ ocamlopt -w +4 -c status.ml
File "status.ml", lines 3-5, characters 12-19:
3 | ............function
4 |   | Active -> "active"
5 |   | _ -> "inactive"
Warning 4 [fragile-match]: this pattern-matching is fragile.
  It will remain exhaustive when constructors are added to type status.

File "status.ml", lines 7-9, characters 17-31:
7 | .................function
8 |   | Active -> true
9 |   | Suspended | Closed -> false
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
  Here is an example of a case that is not matched: Pending

can_log_in, which lists Active, Suspended and Closed explicitly, drew warning 8 naming the new Pending: the compiler found the place that needs a decision. label, with _ -> "inactive", compiled silently in the first run, so a pending account would be labelled inactive without anyone choosing that. Only with -w +4 did OCaml report it: “Warning 4 [fragile-match]: this pattern-matching is fragile. It will remain exhaustive when constructors are added to type status.” Warning 4 is off by default; the manual’s list of warnings describes it as a fragile match.

match with exception handles errors from the value being matched

List.assoc raises Not_found when a key is missing. A case of the form exception Not_found -> … in a match catches that exception, but only when it is raised while computing the value being matched, not inside a branch. The session compares it with try … with, which catches the exception wherever it is raised inside the try:

from session import toplevel

# match e with … | exception E -> … handles an exception raised while computing e, the value being matched, and no
# other; try … with also catches exceptions raised inside the branches.
toplevel("""
let ages = [("asha", 31); ("ravi", 27)];;
let age_or_zero name = match List.assoc name ages with a -> a | exception Not_found -> 0;;
(age_or_zero "ravi", age_or_zero "meera");;
let sum_ages a b = match List.assoc a ages with x -> x + List.assoc b ages | exception Not_found -> -1;;
sum_ages "meera" "ravi";;
sum_ages "asha" "meera";;
let sum_ages_try a b = try List.assoc a ages + List.assoc b ages with Not_found -> -1;;
sum_ages_try "asha" "meera";;
""")

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

# let ages = [("asha", 31); ("ravi", 27)];;
val ages : (string * int) list = [("asha", 31); ("ravi", 27)]
# let age_or_zero name = match List.assoc name ages with a -> a | exception Not_found -> 0;;
val age_or_zero : string -> int = <fun>
# (age_or_zero "ravi", age_or_zero "meera");;
- : int * int = (27, 0)
# let sum_ages a b = match List.assoc a ages with x -> x + List.assoc b ages | exception Not_found -> -1;;
val sum_ages : string -> string -> int = <fun>
# sum_ages "meera" "ravi";;
- : int = -1
# sum_ages "asha" "meera";;
Exception: Not_found.
# let sum_ages_try a b = try List.assoc a ages + List.assoc b ages with Not_found -> -1;;
val sum_ages_try : string -> string -> int = <fun>
# sum_ages_try "asha" "meera";;
- : int = -1

age_or_zero gave (27, 0): Ravi’s age, then 0 for a missing name. sum_ages "meera" "ravi" gave -1, because the first lookup, the value being matched, raised Not_found. But sum_ages "asha" "meera" stopped with Exception: Not_found: the second lookup ran inside the branch, where the exception case does not apply. The try version caught both and returned -1.

That narrowness is the point. A match … with exception handles the failure of one computation and lets errors in the code that uses its result surface, while a broad try around a whole expression can catch an exception the programmer never meant to handle and turn a bug into a silent default.

Practise: patterns, guards and warnings

The questions use the session’s classify, sign, status and ages with new values and new cases. Decide which case matches, which warning appears, or whether an exception escapes, before you check:

Interview questions

Warm-up (2–5 years): why does a match whose guards cover every integer still draw warning 8?

The exhaustiveness check works from the patterns alone. A guard such as when n > 0 is an ordinary expression that could call any function, so the compiler cannot know when it is true, and it counts every guarded case as one that may fail. In match n with 0 -> … | n when n > 0 -> … | n when n < 0 -> … only the pattern 0 is unguarded, so OCaml reports 1 as a possibly unmatched value and adds that some guarded clause may match it. The fix is to make the last case unguarded, such as | _ -> "negative", which the checker can see covers everything left.

Two harder questions follow, about a status match that silently mislabels a new state and about a lookup that hides real errors. Decide what you would check first, then open each first step:

Key takeaways

• Or-patterns match either side, as-patterns bind the whole matched value, guards add a test after the pattern, and cases are tried from the top until one matches; function matches a function’s single argument.
• The exhaustiveness check ignores guards, so a guarded match ends with an unguarded case to be provably complete.
• Warning 8 reports a value no case matches, warning 11 a case that can never run, and warning 4, off by default, a catch-all that will swallow constructors added later.
• A match … with exception case catches an exception from computing the matched value only, while try … with catches it from anywhere inside, including the branches.