In Egison, every pattern matching algorithm is defined by matchers.
`list`

, `multiset`

and `set`

are matchers too, which are defined in standard libraries.

This chapter explains how users can define their original matchers.

`matcher`

Expression

` (matcher {[`*pppattern* *matcher* {[*pdpattern* *formula*] ...}] ...})
*pppattern (primitive pattern pattern)* ::= _ | $ | ,$*value* | <*identifier* *pppattern* ...> | [*pppattern* ... ]
*pdpattern (primitive data pattern)* ::= _ | $*identifier* | <*Identifier* *pdpattern* ...> | [*pdpattern* ... ] | *constants*

Let's think about defining a matcher `unordered-integer-pair`

, which matches with a tuple of 2 integers but ignores the order.

This `unordered-integer-pair`

matcher can be defined as follows.

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 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 syntastic representation of the target data and pattern matching results.

In the example above, the target data `[1 2]`

is syntastically 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 `match-all`

expression, this binding enumrates for the entire results, meaning that first `a`

is bound to `1`

and `b`

to `2`

, and secondly `a`

to `2`

and `b`

to `1`

.

In addition, we can make a "polymorphic" matcher by making it a function that takes matchers and returns a matcher. For example, `unordered-pair`

for an arbitrary matcher can be defined as follows:

`algebraic-data-matcher`

Expression

` (algebraic-data-matcher {<`*identifier* *matcher* ...> ...})

`algebraic-data-matcher`

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 above definition is desugared into the following one:

If you are interested in how our pattern matching works, please check out the chapter *Pattern Matching Mechanism*.