How do you express a set in a program? Probably, most of you represents it as a list. However, a list differs from a set because it does not ignore the order of elements. Then, even if we want to ignore the order, we have to care about it when we represent a set as a list. Data types whose data have no normal form such as sets are called non-free data types. Unfortunately, it had been difficult to do pattern-matching against them in the programming languages before Egison. Egison gives strong pattern-matching expressive power even against those data types. We demonstrate it here with many examples, which contain pattern-matching for lists, multisets, and sets.

---

• Pattern-Matching against Non-Free Data Types!
• Non-Linear Pattern-Matching against Non-Free Data Types!!
• Pattern-Matching with Lexical Scoping!!
• Loop-Patterns

---

Pattern-Matching against Non-Free Data Types!

In this section, we show various basic pattern-matching against collections.

The cons Pattern Constructor

At first, let's execute the following code.

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

All of them say "divide the collection {1 2 3 4} into the head element and the rest collection". If we regard {1 2 3 4} as a list, the head element is 1 and the rest collection is {2 3 4}. However, if we regard the collection as a multiset, the order of the elements is igonored and the notion of a head element changes. If we take the head of the collection as multiset or set, we will get 1, 2, 3, and 4. Egison returns all of them. Note that, the notion of the rest collection differs between multisets and sets.

Nested Pattern Constructors

We can write a nested inductive pattern as follow. They are extracting two elements from the collection.

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

The join Pattern Constructor

There is another pattern-constructor join for collections. join is a pattern that divides 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}]}

You might wonder about the order of results of pattern-matching. Specifically, why is not the result of the first expression as follow?

{[{1 2 3} {}] [{1 2} {3}] [{1} {2 3}] [{} {1 2 3}]}

The reason is there is a case that the target collection is an infinite list. We cannot return any answers if we adopted the latter order.

The snoc and nioj Pattern Constructor

The matcher list has other special pattern constructors to destruct a collection into the tail and the others. The inductive pattern, named snoc, is the "dual" of cons. Of course, since a (multi)set has no order, neither multiset nor set has snoc. Similarly, list also has the "dual", nioj, of join.

(match-all {1 2 3} (list integer) [<snoc $x $xs> [x xs]]) ;=>{[3 {1 2}]} (match-all {1 2 3} (list integer) [<nioj $xs $ys> [xs ys]]) ;=>{[{} {1 2 3}] [{3} {1 2}] [{3 2} {1}] [{3 2 1} {}]}

The arguments of snoc matches with the last element of a target collection and the rest of it. Note that, in Egison, extraction of an element from the tail of a collection is represented in the same way as the head of it. A pattern constructor nioj is similar to join, and used to divide a target collection into two collections. The difference between join and nioj is the order of pattern-matching, as its name suggests. In case of nioj, pattern-matching is executed from the back-side of a collection. The order of pattern-matching is important when we do non-linear pattern-matching, which we will discuss in the next section.

Non-Linear Pattern-Matching against Non-Free Data Types!!

Egison allows programmers to "bind and use" variables in a pattern. A pattern that contains multiple occurrences of the same variables is called a non-linear pattern. Egison is the first programming language that non-linear patterns can be used in pattern-matching for non-free data.

The First Example

The following is the first example of non-linear patterns. The output of this example is the collection of numbers duplicated in the target collection.

(match-all {1 2 3 1 2} (multiset integer) [<cons $n <cons ,n _>> n]) ;=>{1 2 1 2}

Egison executes pattern-matching from left to right, and a bound variable can be referred to in its right side of the pattern. In this example, at first, the variable n is bound to any element of the collection. Then, Egison examines the pattern ,n. It places the right side of $n, it is evaluated to the value where n is bound. When an object matches the pattern ,n, it is equal to the value as integer. Therefore, after successful pattern-matching, n is bound to an element contained at least two in the target collection.

We can write any expression after ,. Non-linear pattern-matching against non-free data types extends the expressive power of the language so much. Please see Poker Hands demonstration.

Pattern-Matching against Nested Data Types

Here is another example. We can write pattern-matching against nested non-free data types such as a list of multisets or a set of sets as the following sample code.

(match-all {{1 2 3 4 5} {4 5 1} {6 1 7 4}} (list (multiset integer)) [<cons <cons $n _> <cons <cons ,n _> <cons <cons ,n _> <nil>>>> n]) ;=>{1 4}

Probably, you understand how strong the pattern-matching of Egison is. In this chapter, we show the inductive patterns of the matchers list, multiset, and set. If you want to make your own matcher or understand matchers more deeply, please read the next chapter Matchers.

Pattern-Matching with Lexical Scoping!!

We can reuse a pattern via a pattern-function. A pattern-function is a function that takes patterns and returns a pattern.

Patterns are not first class objects. So we can NOT replace a pattern with an object, and vice versa. For example, (test _) is illegal, because _ is not an object but a pattern as shown below. However, pattern-functions are first class objects. So we can define pattern-functions and apply it as an argument of a function in anywhere of programs.

Egison programmers reuse a pattern via a pattern-function. Although this restriction seems to be too strict, this makes modularization of patterns clear.

See Mahjong demonstration to see how to use pattern-functions.

Loop-Patterns

Can you write a function comb2 that takes a collection as the argument, and returns the 2-combinations of it? This is an easy exercise, and our answer is as follows.

(define $comb2 (lambda [$xs] (match-all xs (list something) [<join _ <cons $a_1 <join _ <cons $a_2 _>>>> [a_1 a_2]]))) (comb2 {1 2 3 4 5}) ;=>{[1 2] [1 3] [2 3] [1 4] [2 4] [3 4] [1 5] [2 5] [3 5] [4 5]}

Next, can you write a comb3? You will easily rewrite comb2 to comb3 as follows.

(define $comb3 (lambda [$xs] (match-all xs (list something) [<join _ <cons $a_1 <join _ <cons $a_2 <join _ <cons $a_3 _>>>>>> [a_1 a_2 a_3]]))) (comb3 {1 2 3 4 5}) ;=>{[1 2 3] [1 2 4] [1 3 4] [2 3 4] [1 2 5] [1 3 5] [1 4 5] [2 3 5] [2 4 5] [3 4 5]}

If you can, how about comb4, comb5, and so on? Patterns in these combX have the same form, <join _ <cons $a_1 <join _ <cons $a_2 ... _>...>>> and then it seems to be possible to generalize them. We can do such a thing using a loop-pattern.

 (loop $identifier range pattern pattern)

The arguments of a loop-pattern represent an index-variable, a range of the index, a pattern repeated, and a pattern representing the end. When the pattern ran all range, a loop-pattern is "the same as" the last argument. Otherwise, it is "the same as" the third argument substituted itself for ... and the head of the second argument for the index-variable with removing the head of the second argument. It is probably difficult to understand what it means. Then, we give comb as an example, and will describe the meaning of a loop-pattern using the example. It's roughly correct and easier to understand.

(define $comb (lambda [$xs $n] (match-all xs (list something) [(loop $i [1 n] <join _ <cons $a_i ...>> _) (map (lambda [$i] a_i) (between 1 n))]))) (comb {1 2 3 4 5} 3) ;=>{{1 2 3} {1 2 4} {1 3 4} {2 3 4} {1 2 5} {1 3 5} {1 4 5} {2 3 5} {2 4 5} {3 4 5}}

We consider the case n is three. Then, a loop-pattern is

(loop $i {1 2 3} <join _ <cons $a_i ...>> _)

When the range of the index is non-null, a loop-pattern "returns" the third argument regarding ... in the argument as the loop-pattern itself. Since {1 2 3} isn't null, the above example is "evaluated to"

<join _ <cons $a_1 (loop $i [2 3] <join _ <cons $a_i ...>> _)>>

Note that in the "evaluation", the index-variable i is "replaced with" the head of the collection, 1 in the example. Moreover, the collection argument of the loop-pattern loses its head. That is, {1 2 3} is "replaced with" {2 3} Repeating this "evaluation",

<join _ <cons $a_1 <join _ <cons $a_2 <join _ <cons $a_3 (loop $i [3 3] <join _ <cons $a_i ...>> _)>>>>>>

In the case, the second argument of the loop-pattern is null, Egison "evaluates" the last argument _. Then,

<join _ <cons $a_1 <join _ <cons $a_2 <join _ <cons $a_3 _>>>>>>

It is the same as what we used in comb3! Actually, since a loop-pattern is just a pattern, Egison doesn't evaluate a loop-pattern. However, a claim that the above patterns are the same is true. Then, recalling "the result of evaluation", we can use a loop-pattern.

In the above, we omit explanation of restriction. ... must be placed at the end of the second argument. For example, <cons ... <nil>> is prohibited. This restriction decides which loop-patterns a given ... belongs to, and then allows us to write nested loop-patterns.

By the way, we can omit the last argument of a loop-pattern. In such a case, Egison regards the last argument is !_, which is a pattern that no objects match. For example,

(loop $i [1 n] <join _ <cons $a_i ...>>)

is interpreted as

(loop $i [1 n] <join _ <cons $a_i ...>> !_)

See Also ...

We have written a lot of documentations about pattern-matching. Please refer the following articles, too.

• The Concept of Egison
• The 3 Exciting Moments Developing Egison

We also recommend you to read the chapter Pattern-Matching Mechanism, if you are interested in the mechanism pattern-matching inside Egison.

What to do next...

Next Chapter: Matchers Top of Manual Back to Home