The or-pattern (p | q) matches a value v if either p or q match v. It may happen that both p and q match certain values, but that they don’t bind their variables at the same places. OCaml specifies that the left pattern p then takes precedence, but users intuitively expect an angelic behavior, making the ``best'' choice. Subtle bugs arise from this mismatch. When are (p | q) and (q | p) observably different?

To correctly answer this question we had to go back to pattern matrices, the primary technique to compile patterns and analyze them for exhaustivity, redundant clauses, etc. There is a generational gap: pattern matching was actively studied when most ML languages were first implemented, but many of today’s students and practitioners trust our elders to maintain and improve them. Read on for your decadely fix of pattern matching theory!