Patterns occupy important positions in Egison. They are distinguished from the other objects, and form their own rich world. This chapter explains various kinds of patterns and syntax using patterns. To explain the syntax and its operational semantics, we give simple Egison code as examples. Since these chapters are so simple, you perhaps cannot understand the details of Egison. Then, we strongly recommend you to read other chapters after reading this chapter. The readers who want to master pattern-matching should read the next chapter Pattern Matching. If you want to create your own matcher, see the chapter Matchers.

---

• Patterns
• Wildcard
• Pattern Variables
• Indexed Pattern Variables
• Inductive Patterns
• Value Patterns
• Predicate Patterns
• And-Patterns
• Or-Patterns
• Not-Patterns
• Later Patterns
• Sequential Patterns
• Loop Patterns
• Let Patterns
• Syntax Related with Patterns
• match-all Expressions
• match Expressions
• match-lambda Expressions
• match-all-lambda Expressions
• pattern-function Expressions
• matcher Expressions

---

Patterns

In the following, we show various patterns of Egison.

Wildcard

Here, we explain the special pattern wildcard. _ represents a wildcard. Any object matches this pattern.

(match #t bool {[_ <OK>]});=><OK> (match #f bool {[_ <OK>]});=><OK>

Pattern Variables

$identifier

We can bind values to variables in pattern-matching. For this purpose, we use pattern variables. Any object matches this pattern, and then the variable is locally bound to the object.

(match #t bool {[$x x]});=>#t (match {1 2 3} (list integer) {[<nil> #f] [<cons $x $xs> [x xs]]});=>[1 {2 3}]

Indexed Pattern Variables

$identifier_integer 

Indexed pattern variables are special pattern variables. In this pattern, the variable is regarded as an hash, and then the matching object is bound to the value of the hash associated the integer key.

(match 1 something {[$x_1 x]});=>{| [1 1] |} (match {1 2 3} (list integer) {[<cons $x_1 $x_2> x]}) ;=> {| [1 1] [2 {2 3}] |}

Inductive Patterns

<identifier value ...>

Patterns can be defined inductively. The notation of inductive patterns is similar to that of inductive data. The exception is, in inductive patterns, the head of an identifier is lowercase. The behaviour of inductive patterns is defined in a matcher. For eample, the cons pattern constructor is used to divide a collection into an element and the rest collection. The behaviour of inductive pattern cons is defined in each matcher.

(match-all {1 2 3} (list integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}]} (match-all {1 2 3} (multiset integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}] [2 {1 3}] [3 {1 2}]} (match-all {1 2 3} (set integer) [<cons $x $xs> [x xs]]) ;=>{[1 {1 2 3}] [2 {1 2 3}] [3 {1 2 3}]}

The join pattern constructor is used to divide a collection into two collections.

(match-all {1 2 3} (list integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {2 3}] [{1 2} {3}] [{1 2 3} {}]} (match-all {1 2 3} (multiset integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {2 3}] [{2} {1 3}] [{3} {1 2}] [{1 2} {3}] [{1 3} {2}] [{2 3} {1}] [{1 2 3} {}]} (match-all {1 2 3} (set integer) [<join $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{1} {1 2 3}] [{2} {1 2 3}] [{3} {1 2 3}] [{1 2} {1 2 3}] [{1 3} {1 2 3}] [{2 1} {1 2 3}] [{2 3} {1 2 3}] [{3 1} {1 2 3}] [{1 2 3} {1 2 3}] [{3 2} {1 2 3}] [{1 3 2} {1 2 3}] [{2 1 3} {1 2 3}] [{2 3 1} {1 2 3}] [{3 1 2} {1 2 3}] [{3 2 1} {1 2 3}]}

Finally, the nil is a pattern constructor that takes no arguments and matches if a collection is empty.

(match {} (list integer) {[<nil> #t] [_ #f]});=>#t

Value Patterns

,expr

A value pattern is a pattern that matches with objects equal with the content of the pattern. The expression following , can be any kind of expressions.
The equality is defined in each matcher, and then varies by matcher. We shouldn't forget to place , ahead of the pattern.

(match 1 integer {[,1 <OK>] [_ <KO>]});=><OK> (match 0 integer {[,1 <OK>] [_ <KO>]});=><KO> (match {1 2 3} (list integer) {[,{1 2 3} <OK>] [_ <KO>]});=><OK> (match {1 2 3} (list integer) {[<cons _ <cons ,2 _>> <OK>] [_ <KO>]});=><OK> (match {1 4 3} (list integer) {[<cons _ <cons ,2 _>> <OK>] [_ <KO>]});=><KO>

Predicate Patterns

?predicate

A predicate pattern is a pattern that matches with objects which satisfy the predicate following ?. The expression following ? should be a function that takes an argument and return a boolean value.

(match-all {1 2 3 4 5 6} (list integer) [<join $xs <cons ?(lt? $ 4) $ys>> {@xs @ys}]) ;=>{{2 3 4 5 6} {1 3 4 5 6} {1 2 4 5 6}} (match-all {1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987} (multiset integer) [<cons (& ?(lambda [$x] (eq? (modulo x 2) 0)) $x) _> x]) ;=>{2 8 34 144 610}

And-Patterns

(& pattern ...)

An and-pattern is a pattern that matches the object, if and only if, all of the patterns are matched.

(match {1 3 2} (list integer) {[(& <cons ,1 _> <snoc ,2 _>) <OK>] [_ <KO>]}) ;=><OK> (match #t something {[(&) <OK>] [_ <KO>]}) ;=><OK>

We can use and-patterns like as-patterns. For example, any non-empty collection matches the following and-pattern, and then the variable xs is bound to it.

(match {1 2} (list integer) {[(& <cons _ _> $xs) xs] [_ #f]}) ;=>{1 2} (match {} (list integer) {[(& <cons _ _> $xs) xs] [_ #f]}) #f

Or-Patterns

(| pattern ...)

An or-pattern matches with the object, if the object matches one of given patterns.

(match {1 3 3} (list integer) {[(| <cons ,1 _> <snoc ,2 _>) <OK>] [_ <KO>]}) ;=><OK> (match #t something {[(|) <OK>] [_ <KO>]}) ;=><KO>

Not-Patterns

!pattern

A not-pattern matches with a object if the object does not matches the pattern following after !.

(match 1 integer {[,2 #t] [_ #f]});=>#f (match 1 integer {[!,2 #t] [_ #f]});=>#t (match {2 3 4} (multiset integer) {[<cons ,1 _> #t] [_ #f]});=>#f (match {2 3 4} (multiset integer) {[!<cons ,1 _> #t] [_ #f]});=>#t (match {1 1 2} (multiset integer) {[!<cons ,1 _> #t] [_ #f]});=>#f (match {1 1 2} (multiset integer) {[<cons !,1 _> #t] [_ #f]});=>#t

Later Patterns

Warning: Later pattern is deprecated since version 3.10.2. Please use sequential pattern instead.

(later pattern)

A later pattern is used to change the order of the pattern-matching process. Basically, our pattern-matching system processes patterns from left to right in order. However, we sometimes want this order, for example, to refer to the value bound to the right side of pattern variables. A later pattern can be used for such purpose.

(match {1 1 2 3} (list integer) {[<cons (later ,x) <cons x _>> x]}) ;=>1

Sequential Patterns

{pattern ...}

A sequential pattern is a generalization of a later pattern. A sequential pattern is represented as a list of patterns. Pattern matching is executed for each pattern in order. # that appears in a sequential pattern is called later pattern variable. The target data bound to later pattern variables are pattern-matched in the next sequence. When multiple later pattern variables appear, they are pattern-matched as a tuple in the next sequence. It allows us to apply not-patterns for different parts of a pattern at the same time.

(match-all {2 3 1 4 5} (list integer) [{<cons # <cons # <cons $x _>>> [,(+ x 1) #] ,(+ x 2)} "Matched"]) ;=> {"Matched"}

Loop Patterns

Loop patterns are used to express patterns that contains loops and the number of loops changes by the parameters. Please read the next chapter for detail.

Let Patterns

(let {[variable expr] ...} pattern)

This is similar to the let expressions. Each variable is locally bound to each expr, and the variables can be used in the pattern.

(define $f (lambda [$x] (match x (multiset integer) {[(let {[$n (length x)]} <cons ,n <cons ,n _>>) #t] [_ #f]}))) (f {1 2 2});=>#f (f {3 3 2});=>#t (f {1 2 3 4});=>#f (f {1 4 3 4});=>#t

Syntax Related with Patterns

match-all Expressions

(match-all target-expr matcher-expr [pattern expr])

match-all expressions take a single match-clause. match-all expressions return a collection that contains the evaluated value of expr with each result of pattern-matching.

(match-all {1 2 3} (list integer) [<cons $x $xs> [x xs]]);=>{[1 {2 3}]} (match-all {1 2 3} (multiset integer) [<cons $x $xs> [x xs]]) ;=>{[1 {2 3}] [2 {1 3}] [3 {1 2}]} (match-all {1 2 3} (set integer) [<cons $x $xs> [x xs]]) ;=>{[1 {1 2 3}] [2 {1 2 3}] [3 {1 2 3}]}

We have explained about this expression in Concept of Egison.
In the next chapter, there are many examples.

match Expressions

(match target-expr matcher-expr {[pattern expr] ...})

The difference from match-all expressions is match expressions take multiple match-clauses. It tries pattern-matching for each pattern from the head of match-clauses. When pattern-matching succeeds, the expr of the match-clause will be evaluated. Pattern-matching of Egison has multiple results. However, this expression chooses the first result and they are locally bound and then the formula will be evaluated with them.

(match {1 2 3 4} (list integer) {[<nil> #f] [<cons $x $xs> [x xs]]}) ;=>[1 {2 3 4}] (match {1 2 3 4} (set integer) {[<nil> #f] [<cons $x $xs> [x xs]]}) ;=>[1 {1 2 3 4}]

Please also check the Poker Hands demonstration.

match-lambda Expressions

(match-lambda matcher-expr {[pattern expr] ...})

Like a lambda expression, a match-lambda expression creates a function with an argument. Pattern matching is done with the argument. Roughly speaking, (match-lambda X {[Y Z] ...}) and (lambda [$x] (match x X {[Y Z] ...})) are the same.

match-all-lambda Expressions

(match-all-lambda matcher-expr [pattern expr])

Like a mach-lambda expression, a match-all-lambda expression creates a function with an argument. Pattern matching is done with the argument. Roughly speaking, (match-all-lambda X [Y Z]) and (lambda [$x] (match-all x X [Y Z])) are the same. This expression has a simgle match-clause as a match-all expression.

pattern-function Expressions

(pattern-function [variable ...] pattern)

A pattern-function is a function that gets only patterns and returns a pattern. We define it using a pattern-function expression. It allows us to reuse useful patterns.

Please see the following examples. Since a pattern-function has lexical scoping as a normal function by lambda, bindings for pattern-variables in the argument patterns and the body of pattern-functions don't conflict. Then, we don't have to care about which pattern-variable occurs in a pattern-function.

(define $twin (pattern-function [$pat1 $pat2] <cons (& $pat pat1) <cons ,pat pat2>>)) (match-all {1 2 1 3} (multiset integer) [<cons _ (twin $n _)> n]) ;=>{1 1 1 1} (match-all {1 2 1 3} (multiset integer) [<cons _ (twin ,1 _)> #t]) ;=>{#t #t #t #t} (match-all {2 2 1 3} (multiset integer) [<cons _ (twin ,1 _)> #t]) ;=>{}

Although Egison restricts use of patterns in a match-clause, what you can do isn't limited at all.

matcher Expressions

This expression is used to create a matcher. Since this is complicated, we don't explain this expression here, but do in another chapter. If you want to know how to use this expression, see Matchers.

What to do next...

Next Chapter: Pattern Matching Top of Manual Back to Home