Reference

Pattern Matching

Look up syntax, contracts, layouts, algorithms, and exact behavior.

Pattern matching is implemented for primitive, tuple, record, list, fixed-length array, set, map, constructor, and catch-all patterns. A match expression checks the scrutinee once, then checks every arm under an environment extended by variables bound by the pattern. Arm result types must unify, and the match must contain a wildcard, variable catch-all, a tuple or record pattern whose subpatterns are all exhaustive, complete constructor coverage, or complete list coverage with both [] and a catch-all cons arm. Array, set, and map patterns match exact stored lengths and therefore do not make a match exhaustive without a catch-all.

let classify n =
  match n with
  | 0 -> "zero"
  | 1 -> "one"
  | value -> "many"

Primitive and variable patterns. The final variable pattern both binds value and satisfies the catch-all requirement.

let describe point =
  match point with
  | (0, 0) -> "origin"
  | (x, y) -> String.concat (to_string x) (String.concat "," (to_string y))

Tuple destructuring. Tuple patterns match by arity and element type, then bind element values for the arm body.

let rec sum xs =
  match xs with
  | [] -> 0
  | head :: tail -> head + sum tail

List destructuring. List patterns expose the runtime list shape directly: null for empty, or head/tail slots for cons cells.

let main =
  let names = Set.add (Set.add (Set.empty ()) "Ada") "Grace" in
  let years = Map.set (Map.set (Map.empty ()) "Ada" 1815) "Grace" 1906 in
  match (names, years) with
  | ({| "Grace"; "Ada" |}, {| "Grace": year; "Ada": 1815 |}) -> year
  | _ -> 0

Set and map destructuring. Set and map patterns use {| ... |}. They match the stored linked-entry order, which is newest insertion first for the current Set.add and Map.set helpers.

type 'a option = None | Some of 'a
type ('ok, 'err) result = Ok of 'ok | Error of 'err

let score maybe =
  match maybe with
  | None -> 0
  | Some value -> value

let label result =
  match result with
  | Ok name -> String.length name
  | Error code -> code

Constructor destructuring. Algebraic data type declarations create nominal variant type constructors and constructor bindings. Payload constructor patterns bind their payload under the declared, freshly instantiated payload type.

\frac{\Gamma \vdash e_s:\tau_s\quad p_i \sim \tau_s\Rightarrow\Gamma_i\quad \Gamma_i\vdash e_i:\tau}{\Gamma\vdash\texttt{match}\;e_s\;\texttt{with}\;p_i\rightarrow e_i : \tau}

Pattern typing. Each pattern must be compatible with the scrutinee, and each arm body must produce the same result type.

The exhaustiveness rule is conservative. The checker does not attempt full finite-domain analysis for bool, literals, or every possible array length. Instead, it requires a catch-all pattern, a tuple or record pattern whose nested patterns are all catch-alls, or the standard list split of [] plus a catch-all cons arm. Fixed-length array patterns are useful for destructuring known shapes, but they do not make a match exhaustive by themselves.

The backend stores the scrutinee in a scratch local, then emits a chain of WebAssembly conditionals. Wildcard, unit, and variable patterns can immediately produce their body. Literal patterns compare the scrutinee against the literal representation. Tuple patterns test the tuple arity, recursively test nested element patterns, and bind variables from fixed element offsets. Record patterns test the field count, recursively test field patterns in sorted-label order, and bind variables from fixed field offsets. Array patterns test the array pointer and length, then recurse through fixed element offsets. List patterns test the pointer for null or non-null, then bind head and tail from the cons cell before evaluating the arm body. Set and map patterns walk the linked entries in stored order, testing each item or key/value pair and requiring the pattern length to consume the whole collection. Constructor patterns test the constructor tag and bind the payload slot when the constructor carries one.

PInt, PFloat, PString, PBool, and PUnit unify the scrutinee with the matching primitive type.
PTuple unifies the scrutinee with a tuple type of the same arity and checks each element pattern against the corresponding element type.
PRecord unifies the scrutinee with a record type containing the same labels and checks each field pattern against the matching field type.
PArray unifies the scrutinee with an array type, checks every element pattern against the shared element type, and matches only arrays of the same length.
PListNil unifies the scrutinee with a list type and matches only the empty list; PListCons unifies the head with the element type and the tail with the same list type.
PSet unifies the scrutinee with a set type and checks each stored-entry pattern against the set element type.
PMap unifies the scrutinee with a map type and checks each key pattern against the key type and each value pattern against the value type.
PConstructor unifies the scrutinee with the constructor's nominal variant type and checks any payload pattern against the declared payload type.
PWildcard accepts any scrutinee type and binds nothing.
PVar accepts any scrutinee type and binds the variable to that type in the arm body.
Missing catch-all arms are rejected before code generation.

Pattern Matching

Continue exploring