25 Pattern Matching Syntax and Semantics

Syntax

match e with
    | p1 -> e1
    | p2 -> e2
    | ...
    | pn -> en

p is a new syntactic class, a pattern expression.

Evaluation Semantics

• If e ==> v
  • and pi is the first pattern, top-to-bottom left-to-right, that matches v
  • and ei ==> vi
  • then (match e ...) ==> vi
• If no patterns match, an exception is raised

Type-Checking Semantics

• If e and pi have type ta
• and ei has type tb
• then the entire match expression has type tb.

Basic matching syntax

• x (any identifier)
• _ (wildcard)
• any constant

How does matching work?

• A constant matches itself.
• An identifier (also known as a pattern variable), will match anything, and bind itself to the value
• The wildcard (_) will match anything.
• Each data type has it's own matching pattern
  • []
  • p1 :: p2 etc.
  • [pi; p2] etc.
  • (p1, p2] etc.
  • {f1 = p1; f2 = p2} etc.