# Pattern Matching¶

## Expressions for pattern matching¶

### matchAll expression¶

A matchAll expression takes a target, a matcher and one or more match clauses. It tries pattern matching for all match clauses, and returns a collection of the evaluation result of the body for all successful result of pattern matching.

matchAll [1, 2, 3] as list integer with
| $x ::$xs -> (x, xs)
---> [(1, [2, 3])]

matchAll [1, 2, 3] as multiset integer with
| $x ::$xs -> (x, xs)
---> [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]

matchAll [1, 2, 3] as set integer with
| $x ::$xs -> (x, xs)
---> [(1, [1, 2, 3]), (2, [1, 2, 3]), (3, [1, 2, 3])]


When none of the match clauses successfully pattern-matches, matchAll returns an empty collection [].

matchAll [] as list integer with
| $x ::$xs -> (x, xs)
---> []


You can write more than one match clauses. In that case, every match clause must start with | and the | of all match clauses must be vertically aligned.

matchAll [1, 2, 3] as multiset integer with
| [] -> -1
| $x ::$xs -> x


When there is only one match clause, the | can be omitted.

matchAll [1, 2, 1, 3] as multiset integer with twin $n _ -> n ---> [1, 1] matchAll [2, 2, 1, 3] as multiset integer with _ :: twin #1 _ -> True ---> []  Like anonymous functions, a pattern function has lexical scope for the pattern variables. Therefore, bindings for pattern variables in the argument patterns and the body of pattern functions don’t conflict. ## Patterns¶ ### Wildcard pattern¶ Wildcard patterns are denoted by _. It can match with any values and the matched value will be discarded. match [1, 2, 3] as list something with | _ -> "OK" ---> "OK"  ### Pattern variable¶ We can bind values to variables in pattern matching with pattern variables. It is denoted as a variable prefixed with $. Any object matches pattern variables and the variable is locally bound to the object.

match True as bool with

match 1 as something with $x_1 -> x ---> {| (1, 1) |} match [1, 2, 3] as list integer with$x_1 :: $x_2 -> x ---> {| (1, 1), (2, [2, 3]) |}  ### Inductive pattern¶ Inductive pattern is an analogy of inductive data. An inductive pattern consists of a pattern constructor and multiple (zero or more) argument patterns. The names and behaviors of pattern constructors are defined by matchers. In the following example, snoc is a pattern constructor defined in the list matcher, and $x and $xs is applied to the pattern constructor. matchAll [1, 2, 3] as list integer with snoc$x $xs -> (x, xs) ---> (3, [1, 2])  The nil pattern [] and the pattern infixes such as :: and ++ are also implemented as pattern constructors. ### Value pattern¶ A value pattern is written as #expr, where expr can be any expression. An object obj can match a value pattern #expr only if the evaluation result of obj is equal to that of expr. This equality is defined by the given matcher. match 1 as integer with | #1 -> OK | _ -> KO ---> OK match 0 as integer with | #1 -> OK | _ -> KO ---> KO match [1, 2, 3] as list integer with | #[1, 2, 3] -> OK ---> OK match [1, 2, 3] as multiset integer with | #[2, 1, 3] -> OK ---> OK  ### Predicate pattern¶ A predicate pattern is a pattern that matches with an object when it satisfies the predicate following ?. The expression following ? should be a unary function that returns a boolean. matchAll [1..6] as list integer with |$xs ++ ?(< 4) :: $ys -> xs ++ ys ---> [[2, 3, 4, 5, 6], [1, 3, 4, 5, 6], [1, 2, 4, 5, 6]] matchAll [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377] as multiset integer with | ?(\x -> modulo x 2 == 0) &$x -> x
---> [2, 8, 34, 144]


### And-pattern¶

An and-pattern p1 & p2 is a pattern that matches the object if and only if both of the pattern p1 and p2 are matched.

match [1, 3, 2] as list integer with
| (#1 :: _) & snoc #2 _ -> OK
| _                     -> KO
---> OK


We can use and-patterns like as-patterns in Haskell. For example, a pattern (_ :: _) & $xs matches with any non-empty collections and binds it to the variable xs. match [1, 2] as list integer with | (_ :: _) &$xs -> xs
---> [1, 2]

match [] as list integer with
| (_ :: _) & $xs -> xs ---> pattern match failure  ### Or-pattern¶ An or-pattern p1 | p2 matches with the object if the object matches with p1 or p2. match [1, 3, 3] as list integer with | (#1 :: _) | snoc #2 _ -> OK | _ -> KO ---> OK  ### Not-pattern¶ A not-pattern !p matches with the object if the object does not match the pattern p. match 1 as integer with !#2 -> True ---> True -- Returns True if and only if the collection does not contain 1 f := \match as multiset integer with | !(#1 :: _) -> True | _ -> False -- Returns True if and only if the collection has an element other than 1 g := \match as multiset integer with | !#1 :: _ -> True | _ -> False f [2, 3, 4] ---> True f [1, 2, 3] ---> False g [1, 2, 3] ---> True g [1, 1, 1] ---> False  ### Sequential pattern¶ See Sequential Patterns in the tutorial. ### Loop pattern¶ See Loop Patterns in the tutorial. ### Let pattern¶ A let pattern allows binding expressions to variables inside the pattern. The variables bound in the let pattern can be used in the body of the let pattern. f x := match x as multiset integer with | let n := length x in #n :: #n :: _ -> True | _ -> False f [1, 2, 2] ---> False f [3, 3, 2] ---> True f [1, 2, 3, 4] ---> False f [1, 4, 3, 4] ---> True  ## Matchers¶ ### something matcher¶ something is the only built-in matcher. Only variable pattern and wildcard patterns can be used for something matcher; it does not decompose the target object. match [1, 2, 3] as something with$x -> x ---> [1, 2, 3]
match [1, 2, 3] as something with _  -> True ---> True
match [1, 2, 3] as something with $x :: _ -> x ---> Error  ### Defining matcher with matcher expression¶ This subsection describes how to define a matcher with matcher expression. Let’s think about defining a matcher unorderedIntegerPair, which matches with a tuple of 2 integers ignoring the order. matchAll (1, 2) as unorderedIntegerPair with pair$a $b -> (a, b) ---> [(1, 2), (2, 1)]  This unorderedIntegerPair matcher can be defined as follows. unorderedIntegerPair := matcher | pair$ $as (integer, integer) with | ($x, $y) -> [(x, y), (y, x)] |$ as something with
| $tgt -> [tgt]  Line 3 and 4 corresponds with the case where we want to decompose the tuple, and line 5 and 6 is for the case where we don’t want to. The expression pair$ $ in line 3 is a primitive pattern pattern (pattern for patterns) and it defines a pattern constructor named pair, which enables the pattern expression like pair$a $b. The following (integer, integer) indicates that the both of matched 2 terms should be recursively pattern-matched by using integer matcher. The expression ($x, $y) -> [(x, y), (y, x)] in line 4 defines the correspondense between the syntactic representation of the target data and pattern matching results. The ($x, $y) in line 4 is called primitive data pattern. In the example above, the target data (1, 2) is syntactically matched with ($x, $y), making the variable x bound to 1 and y to 2. As a result, the pattern matching result (specified with [(x, y), (y, x)]) will be [(1, 2), (2, 1)]. Then, variable a and b in the pattern expression pair$a $b are bound to one of the pattern matching result. Since it is a matchAll expression, this binding enumrates for the entire results, meaning that the first a is bound to 1 and b to 2, and secondly a to 2 and b to 1. This unorderedIntegerPair matcher only works for integer tuples; however, we can make it “polymorphic” by making it a function that takes matchers and returns a matcher. For example, unorderedPair for an arbitrary matcher can be defined as follows: unorderedPair m := matcher | pair$ $as (m, m) with | ($x, $y) -> [(x, y), (y, x)] |$ as something with
| $tgt -> [tgt] -- Examples match ([1, 2], [3, 4]) as unorderedPair (multiset integer) with | pair (#4 :: _) _ -> True ---> True  ### algebraicDataMatcher expression¶ algebraicDataMatcher is a convenient syntax sugar for defining normal matchers, which decompose data accordingly to their data structure. For example, the following code defines a matcher for terms in untyped lambda calculus. The first identifiers in each line of the algebraicDataMatcher (var, abs and app) must start with a lower case alphabet. term := algebraicDataMatcher | var string -- variable | abs string term -- lambda abstraction | app term term -- application  The above definition is desugared into the following one: term := matcher | var$ as string with
| Var $x -> [x] | _ -> [] | abs$ $as (string, term) with | Abs$x $t -> [(x, t)] | _ -> [] | app$ $as (term, term) with | App$s $t -> [(s, t)] | _ -> [] |$ as something with
| \$tgt -> [tgt]