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, 3] as multiset integer with $x :: _ -> x
match
expression¶
match
expressions are similar to matchAll
expressions except that it returns only one value.
In fact, the return value of a match
expression is defined as the first element of the return value of its corresponding matchAll
expression.
match [1, 2, 3] as multiset integer with
| $x :: $xs -> (x, xs)
---> (1, [2, 3])
When none of the match clauses successfully pattern-matches, it will raise an error.
match [1, 2, 3] as multiset integer with
| [] -> "OK"
---> Failed pattern match in: <stdin>
\matchAll
and \match
¶
\matchAll
and \match
are handy syntax sugar for the combination of anonymous function and matchAll
/match
expressions.
The syntax of \matchAll
expression is similar to that of matchAll
except that it doesn’t need the target.
A \matchAll
expression is desugared into an anonymous function whose body is matchAll
and whose argument is the target of matchAll
.
For example,
\matchAll as matcher with
| pattern1 -> expr1
| pattern2 -> expr2
is desugared into the following expression.
\x ->
matchAll x as matcher with
| pattern1 -> expr1
| pattern2 -> expr2
The semantics of \match
is similar.
matchAllDFS
and matchDFS
¶
matchAllDFS
and matchDFS
are variants of matchAll
and match
, respectively.
See Controlling the order of pattern matching for the description.
Pattern functions¶
A pattern function is a function that takes patterns and returns a pattern. Pattern functions allows us to reuse useful combination of patterns.
The syntax of pattern function is similar to that of anonymous function except that it uses double arrow =>
instead of the sigle arrow ->
.
Also, the argument pattern must be prefixed with a ~
in the body of the pattern function.
This is to distinguish the argument with nullary pattern constructor.
The application of pattern functions is written in the same manner as the application of pattern constructors.
-- Defining a pattern function 'twin'
def twin := \ pat1 pat2 => ($pat & ~pat1) :: #pat :: ~pat2
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
| $x -> x
---> True
match [1, 2, 3] as list integer with
| $x :: $xs -> (x, xs)
---> (1, [2, 3])
Indexed pattern variable¶
Indexed pattern variables $x_n
(n
denotes integers) are special pattern variables.
When an indexed pattern variable $x_n
appears in the pattern, Egison creates a hash map and binds it to the variable x
.
An object matched to $x_i
is associated with the key i
in the hash x
.
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
def f :=
\match as multiset integer with
| !(#1 :: _) -> True
| _ -> False
-- Returns True if and only if the collection has an element other than 1
def 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.
def 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.
def 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:
def 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.
def term :=
algebraicDataMatcher
| var string -- variable
| abs string term -- lambda abstraction
| app term term -- application
The above definition is desugared into the following one:
def 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]