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.