2Egison早巡り

本章は，パターンマッチ指向プログラミングのためのEgisonの機能を一通り紹介する． 本章を理解すれば，Egisonのパターンマッチの仕様はほぼ一通り理解したことになるはずである．

本章の前半（2.1節，2.2節，2.3節，2.4節，2.5節）では，パターンマッチのための構文を紹介する． Egisonのパターンマッチは，非自由データ型に対するパターンマッチを実現するために，複数のマッチ結果をもつ非線形パターン（パターン変数に束縛した値を同じパターン内で参照するパターン）を効率的に処理できるように設計されている． 本章の前半では，この機能がどのように構文として表現できるのか解説する．

本章の後半（2.6節，2.7節，2.8節，2.9節，2.10節）では，さまざまな組み込みパターンを紹介する． そのうち後半で紹介されるループ・パターンや，シーケンシャル・パターンはEgison以外のプログラミング言語にはまだ実装されていないパターンである． これらの組み込みパターンは，最初は特殊でアドホックにみえるかもしれない． これらの組み込みパターンの意味は，初見で完全に理解できなくても問題ない． 本書の後半で，これらのパターンの実用例が紹介されたときに，本章にもどってきてほしい．

2.1matchAll式によるパターンマッチ

パターンマッチを記述するためのいくつかの構文をEgisonは提供している． そのうちもっとも基本的な構文はmatchAll式である．

matchAll [1,2,3] as list something with
| $x :: $ts -> (x, ts)
-- [(1,[2,3])]

matchAll式は，ターゲット（上記の場合， [1,2,3] ），マッチャー（上記の場合，list something），1つ以上のマッチ節（上記の場合，$x :: $xs -> (x,xs)）から構成される． マッチ節は，パターン（上記の場合，$x :: $xs）とボディ（上記の場合，(x,xs)）からなる． matchAll式は，既存のプログラミング言語のマッチ式と同様に，ターゲットとパターンのパターンマッチを試みて，もしマッチしたらそのマッチ節のボディを評価する．

EgisonのmatchAll式の特徴は，（1）結果としてリストを返すことと，（2）マッチャーという追加の引数をとることにある． （1）の特徴は，複数の結果をもつパターンマッチをサポートするための特徴である． matchAll式は複数のパターンマッチの結果すべてについてボディを評価して，その結果を集めてリストとして返す． 上記の例のパターンに使われている::はコンス・パターン（cons pattern）と呼ばれる，リストを先頭の要素と残りのリストに分解するパターンコンストラクタである． そのため，上記の例の場合はパターンマッチの結果が一つであるので，長さが\(1\)のリストを返している． （2）の特徴は，パターンマッチアルゴリズムの拡張性とパターンの多相性を実現するための特徴である． マッチャーはEgison以外の言語ではみられない独自のオブジェクトで，パターンマッチアルゴリズムを保持するためのオブジェクトである． マッチャーによるパターンの多相性については，2.4節で扱う． --で始まる行はコメントである． 本書において，プログラム直後のコメントはプログラムの実行結果を記述するものとする．

matchAll式の文法の詳細についてもう少し説明する． asとwithというキーワードでマッチャーは囲まれる． matchAll式はマッチ節を複数とることができる．matchAll \(t\) as \(m\) with \(c_1\) \(c_2\) \(...\)は，(matchAll \(t\) as \(m\) with \(c_1\)) ++ (matchAll \(t\) as \(m\) with \(c_2\)) ++ \(...\)と同値である． マッチ節の先頭には|がつく．マッチ節が複数ある場合，最初のマッチ節の前にも|は必須である． |はマッチ節が複数行に渡る場合にプログラムの可読性を高める． マッチ節中のパターンとボディは->で区切られる．

matchAll target as matcher with
| pattern1 -> body1
| pattern2 -> body2
...

マッチ節が1つであるときは，下記のようにマッチ節の前の|を省略することができる．

matchAll target as matcher with pattern -> body

複数の結果をもつパターンマッチの例を紹介する． 下記のmatchAll式のパターンで使われている++はジョイン・パターン（join pattern）と呼ばれる，リストを先頭部分のリストと残りのリストに分解するパターンコンストラクタである． ジョイン・パターンによる複数の分解のすべてについて，matchAll式はボディ式を評価する．

matchAll [1,2,3] as list something with
| $hs ++ $ts -> (hs, ts)
-- [([], [1, 2, 3]), ([1], [2, 3]), ([1, 2], [3]), ([1, 2, 3], [])]

2.2値パターンと述語パターンによる非線形パターンの表現

matchAll式は，非線形パターンと組み合わせたときにその本領を発揮する． たとえば，以下の非線形パターンは，対象のコレクションが同値な要素のペアを含む場合にパターンマッチに成功する．

matchAll [1,2,3,2,4,3] as list integer with
| _ ++ $x :: _ ++ #x :: _ -> x
-- [2,3]

値パターン(value pattern)は非線形パターンを表現するために重要な役割を果たす． 値パターンは，値パターンの中身とターゲットが等しいかどうかチェックする． 値パターンの先頭には，#が付加される． #の後ろには任意の式を書くことができる． #に続く式は，その値パターンの左側に現れたパターン変数に束縛された値を参照しながら評価される． この動作を実現するため，Egisonのパターンは左から右に順番に処理されることが決まっている． その結果，$x :: #x :: _のようなパターンは妥当であるが，#x :: $x :: _は正しく動かない． （どうしてもパターンの右側に現れるパターン変数の値を参照したいという場合は，2.8節で紹介するシーケンシャル・パターンが使える．）

ほかの非線形パターンの例として，双子素数のパターンマッチを紹介する． 双子素数とは，差が2であるような素数のペアのことをいう． primesには素数の無限列が束縛されている．primesはEgisonの組み込みライブラリで定義されている． このmatchAll式は，素数の無限列からすべての双子素数を順番に抜き出す． Egisonは静的型付けシステムを備えているが，型推論により型アノテーションを省略できる． 必要に応じてdef twinPrimes : [(Integer, Integer)] := ...のように型を明示的に指定することもできる．

def twinPrimes := matchAll primes as list integer with
  | _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)

take 8 twinPrimes
-- [(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]

パターンマッチのときに，同値性よりも一般的な条件を使いたいことがある． 述語パターン(predicate pattern)はそのために用意されている組み込みパターンである． 述語パターンは，中身の述語にターゲットを適用した結果がTrueである場合，パターンマッチに成功するパターンである． 述語パターンの先頭は，?からはじまり，?のあとには1引数の述語が続く．

def twinPrimes := matchAll primes as list integer with
  | _ ++ $p :: ?(\q -> q = p + 2) :: _ -> (p, p + 2)

2.3バックトラッキングによる効率的な非線形パターンマッチ

Egison内部のパターンマッチアルゴリズムは，非線形パターンを効率的に処理するためにバックトラッキングを使う．

matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ -> x
-- `\color{P@GrayComment}{Returns}` [] `\color{P@GrayComment}{in O(n\^{}2)}`
matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ ++ #x :: _ -> x
-- `\color{P@GrayComment}{Returns}` [] `\color{P@GrayComment}{in O(n\^{}2)}`

上記の2つのマッチ式は，\(1\)から\(n\)までの整数のリストから同じ要素の2つ組，3つ組をそれぞれ抽出する． 同じ要素の2つ組も3つ組もターゲットのリストには含まれていないため，これらのmatchAll式は両方とも空リストを返す． 2つ目のmatchAll式が評価されるとき，Egison処理系は2つ目の#xのパターンマッチまで行き着かない． 1つ目の#xでパターンマッチが失敗するからである． （2.2節で述べたようにEgisonのパターンマッチはパターンを左から右へ順番に処理する．） それゆえ，両方のmatchAll式の時間計算量は同じである． Egison内部のパターンマッチアルゴリズムについては，第5章で詳しく解説する．

2.4マッチャーによるパターンの拡張性と多相性

パターンの拡張性以外のマッチャーがもたらすメリットに，パターンのアドホック多相性がある． パターンのアドホック多相性とは，::や++などといったパターン・コンストラクタを，リストや多重集合などといった複数のマッチャーに対して，同じ名前で使うことができる性質のことである． パターンのアドホック多相性は，さまざまな非自由データ型のパターンマッチを許すEgisonにおいて非常に重要である． なぜなら，1つのデータがプログラムの複数の箇所でそれぞれ違う非自由データ型としてパターンマッチされることが多々あるためである． たとえば，リストは多重集合，集合としてパターンマッチされることがある． パターンの多相性によって，パターンコンストラクタの名前の数を大幅に減らすことができる．

下記のmatchAll式は， コレクション（collection）[1,2,3]をターゲットとして，それぞれ違うマッチャーを使って同じコンス・パターンでパターンマッチしている． ここでコレクションという言葉を使ったが，これは今までリストと呼んでいたもののことを指している． コレクションは，リストとしてパターンマッチされることもあれば，多重集合や集合としてパターンマッチされることがある． そのため，リストや多重集合，集合などとして扱われることがあるデータを総称して以降コレクションと呼ぶ． マッチャーがリストの場合，コンス・パターンは，先頭の要素と残りの要素のコレクションに分解する． マッチャーが多重集合の場合，コンス・パターンは，ある要素と残りの要素のコレクションに分解する． マッチャーが集合の場合，コンス・パターンは，ある要素とターゲットのコレクション自身に分解する． 集合のこの挙動は，集合をすべての要素を無限個含むコレクションとしてとらえれば，自然な仕様と考えることができる． （\(\infty - 1 = \infty\)と考える．）

matchAll [1,2,3] as list something with $x :: $xs -> (x,xs)
-- [(1,[2,3])]
matchAll [1,2,3] as multiset something with $x :: $xs -> (x,xs)
-- [(1,[2,3]),(2,[1,3]),(3,[1,2])]
matchAll [1,2,3] as set something with $x :: $xs -> (x,xs)
-- [(1,[1,2,3]),(2,[1,2,3]),(3,[1,2,3])]

パターンの多相性は特に値パターンを表現するときに便利である． コンス・パターンなどのコンストラクタパターンと同様に値パターンの挙動もマッチャーによって異なる． たとえば，[1,2,3] == [2,1,3]のようなコレクション同士の同値性は，コレクションをリストとしてみなすか多重集合としてみなすかによって変わってくる． しかしEgisonでは，パターンのアドホック多相性のおかげで，両者の同値性を同じパターンでチェックできる． 値パターンの多相性によって，非自由データ型を扱うプログラムが大幅に読みやすくなる．

matchAll [1,2,3] as list integer with #[2,1,3] -> "Matched" -- []
matchAll [1,2,3] as multiset integer with #[2,1,3] -> "Matched" -- ["Matched"]

2.5matchAllDFS式によるパターンマッチ結果の順序の制御

matchAll式は可算無限個の結果すべてを列挙するように内部のパターンマッチアルゴリズムが設計されているが， その列挙の仕方は処理系によって決められている． 場合によっては，この順序が重要であることがある．

典型的な例を紹介する． 以下のmatchAll式はすべての自然数のペアを列挙する． take関数を使って先頭\(8\)個のペアを取り出している． matchAllはパターンマッチの探索木をすべてのノードをたどるために幅優先探索する．この幅優先探索の詳細については，Egisonパターンマッチの設計についての論文[1]の5.2節にて詳しく解説されている. その結果，パターンマッチの結果の順序は以下のようになる．

take 8 (matchAll [1..] as set something with
        | $x :: $y :: _ -> (x,y))
-- [(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(2,3),(3,2)]

上記の順序は，無限に大きい可能性がある探索木をすべてたどる場合に適している． しかし，この順序が好ましくない場面もある． パターンマッチの探索木を深さ優先探索するmatchAllDFSは，このような場面のために用意されている．

take 8 (matchAllDFS [1..] as set something with
        | $x :: $y :: _ -> (x,y))
-- [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8)]

たとえば，以下のようにパターンマッチによりconcat関数を定義する場合，matchAllDFS式を使うことで正しい順番で結果のコレクションを生成できる．

def concat xss := matchAllDFS xss as list (list something) with
  | _ ++ (_ ++ $x :: _) :: _ -> x

もし，matchAllDFSの代わりにmatchAllを使ってしまうと，以下のように，引数のリストのリストの要素を交互に列挙してしまう．

take 10 (matchAll [[1..], map neg [1..]] as list (list something) with
         | _ ++ (_ ++ $x :: _) :: _ -> x)
--  [1,2,-1,3,-2,4,-3,5,-4,6]

2.6andパターン・orパターン・notパターン

andパターンやorパターン，notパターンといった論理パターンは，パターンの表現力を広げるために重要な役目を果たす． andパターンは，2つのパターンをとり，両方のパターンがマッチする場合，そのandパターン自体がパターンマッチに成功する． orパターンは，2つのパターンをとり，どちらか1つのパターンがマッチする場合，そのorパターン自体がパターンマッチに成功する． notパターンは，1つのパターンをとり，そのパターンのマッチに失敗した場合，notパターン自体のパターンマッチに成功する．

andパターンとorパターンの使用例として，三つ子素数を抽出するパターンマッチを紹介する． 三つ子素数とは，\((p,p+2,p+6)\)または\((p,p+4,p+6)\)の形で表される素数の三つ組のことをいう． orパターン(#(p + 2) | #(p + 4))は，\(p+2\)と\(p+4\)の両方にマッチするために使われている． andパターン((#(p + 2) | #(p + 4)) & $m)は，\(p+2\)または\(p+4\)にマッチした場合，その値を$mに束縛するために使われている． このandパターンの使い方は，Haskellに提供されているasパターンの使い方に似ている．

def primeTriples := matchAll primes as list integer with
  | _ ++ $p :: ((#(p + 2) | #(p + 4)) & $m) :: #(p + 6) :: _
  -> (p, m, p + 6)

take 6 primeTriples -- [(5,7,11),(7,11,13),(11,13,17),(13,17,19),(17,19,23),(37,41,43)]

notパターンは，その名前が示すとおり，ターゲットがパターンとマッチしない場合にパターンマッチに成功する． notパターンの先頭には!が付加され，!の後に任意のパターンが続く． 以下のmatchAllは双子素数でない隣り合う素数のペアを列挙する． notパターン!#(p + 2)は，\(p+2\)以外の値にマッチするパターンを表現している．

take 10 (matchAll primes as list integer with
         | _ ++ $p :: (!#(p + 2) & $q) :: _ -> (p, q))
-- [(2,3),(7,11),(13,17),(19,23),(23,29),(31,37),(37,41),(43,47),(47,53),(53,59)]

2.7ループ・パターン

ループ・パターン（loop pattern）はパターンの複数回の繰り返しを表現するための組み込みパターンである． ループ・パターンは正規表現のクリーネスター演算子（*）の拡張である．

ターゲットのコレクションの2つの要素の組み合わせを列挙するパターンマッチを考えることからはじめる． これは以下のようなmatchAll式で記述できる．

def comb2 xs := matchAll xs as list something with
  | _ ++ $x_1 :: _ ++ $x_2 :: _ -> [x_1, x_2]

comb2 [1,2,3,4] -- [[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]]

Egisonはこの例の中の$x_1と$x_2のように，パターン変数に添字を付加することを許す．このため，Egisonではsnake_caseによって命名された変数を使うことができない． これらは添字付き変数と呼ばれ，\(x_1\)や\(x_2\)のような数式に対応する． _のあとに続く式は，添字と呼ばれ，整数に評価される必要がある． x_i_j_kのように任意個の添字を変数に付加することができる． 添字付き変数$x_iに値が束縛されたとき，もし変数xにまだ何も束縛されていなかった場合に，Egison処理系は，連想配列を生成し，xに束縛する． この連想配列のキーは整数iであり，それに対応する値は添字付き変数$x_iにマッチした値である． 変数xにすでに連想配列が束縛されている場合には，新しいキーとバリューのペアがこの連想配列に追加される．

上記のcomb2の\(2\)を\(n\)に一般化してみよう． ここで，ループ・パターンを使うことができる．

def comb n xs := matchAll xs as list something with
             | loop $i                 -- `\color{P@GrayComment}{index variable}`
                    (1, n)             -- `\color{P@GrayComment}{index range}`
                    (_ ++ $x_i :: ...) -- `\color{P@GrayComment}{repeat pattern}`
                    _                  -- `\color{P@GrayComment}{terminal pattern}`
             -> map (\i -> x_i) [1..n]

comb 2 [1,2,3,4] -- [[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]]
comb 3 [1,2,3,4] -- [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

ループ・パターンは，添字変数，添字範囲，繰り返しパターン，終端パターンを引数にとる． 添字変数（上記の場合，$i）は，現在の繰り返し回数を保持する変数である． 添字範囲（上記の場合，(1, n)）は，添字変数が動く範囲を指定するために使われる． 添字範囲は，開始値と終了値のペアである． 繰り返しパターン（上記の場合，(_ ++ $x_i :: ...)）は，添字変数が添字範囲のなかにいる間，繰り返されるパターンである． 終端パターン（上記の場合，_）は，添字変数が添字範囲の外に動いたときに展開されるパターンである． 繰り返しパターンの中では，三点リーダーパターン ... を使うことができる． 繰り返しパターンや終端パターンは，三点リーダーパターンの場所に展開される． 三点リーダーパターンで繰り返しパターン展開されるとき，添字変数の値がインクリメントされる． たとえば，\(n=3\)のとき，上記のループ・パターンは，以下のように展開される．

(loop $i (1, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: (loop $i (2, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: _ ++ $x_2 :: (loop $i (3, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: _ ++ $x_2 :: _ ++ $x_3 :: (loop $i (4, 3) (_ ++ $x_i :: ...) _)
_ ++ $x_1 :: _ ++ $x_2 :: _ ++ $x_3 :: _

上記のループ・パターンの繰り返し回数は定数だった． しかし，添字範囲の終了値を整数値でなくパターンにすることにより，ターゲットによりループ・パターンの繰り返し回数が変わるようにすることができる． 添字範囲の終了値がパターンである場合，三点リーダーパターンは繰り返しパターンと終端パターンの両方に展開される． 三点リーダーパターンが終端パターンに展開されたときの繰り返し回数が，添字範囲の終了値のパターンとパターンマッチされる． 以下のループ・パターンは，ターゲットのコレクションの先頭部分を列挙する．

matchAll [1,2,3,4] as list something with
| loop $i (1, $n) ($x_i :: ...) _ -> map (\i -> x_i) [1..n]
-- [[],[1],[1,2],[1,2,3],[1,2,3,4]]

上記，2通りの添字範囲の指定を紹介したが，これらは下記のように，より一般的な添字範囲の指定方法に展開される． (1, n)は下記の3つ目のケースに，(1, $n)は下記の4つ目のケースに対応する．

(`start`)                  <=> (`start`, [`start`..], _)
(`start`, `end-list`)      <=> (`start`, `end-list` _)
(`start`, `end`)           <=> (`start`, [`end`] _)
(`start`, `terminal-pat`)  <=> (`start`, [`start`..], `terminal-pat`)

一般に，添字範囲は，開始値と終了値のリスト，終端パターンの3つからなる． 開始値は省略できない． 終了値のリストが省略された場合は，開始値から始まる無限リストが終了値のリストとなる． 終了値のリストがリストでなく，整数値であった場合，その整数値だけを含むリストに変換される． 終端パターンが省略された場合，ワイルドカードが補完される． たとえば，(1, n)は(1, [n], _)，(1, $n)は(1, [1..], $n)にそれぞれ展開される．

ループ・パターンは，ツリーやグラフのパターンマッチをするときに特によく使われる． 第3章3.4節でそのような例を紹介する． 形式的なループ・パターンの構文と意味論は，ループ・パターンの論文 [2]で解説されている．

2.8シーケンシャル・パターン

Egison処理系はパターンを左から右に順番に処理する． しかし，パターンの右側で束縛されるパターン変数の値を参照したいなど，この処理の順番を変えたいことがある． シーケンシャル・パターン(sequential pattern)はそのために用意された組み込みパターンである．

シーケンシャル・パターンは，パターンマッチの処理の順番をユーザーが変えることを許す． シーケンシャル・パターンは，パターンのリストとして表現される． パターンマッチは，リストの先頭から順番に実行される． 以下のシーケンシャルパターンは，リストの3つ目の要素，1つ目の要素，2つ目の要素の順番でターゲットのリストをパターンマッチする．

matchAll [2,3,1,4,5] as list integer with
| {     @    ::     @    :: $x :: _,
   (#(x + 1),       @    ),
                 #(x + 2)}
-> "Matched" -- ["Matched"]

シーケンシャル・パターン中に現れる@は，後回しパターン変数（later pattern variable）と呼ばれる． 後回しパターン変数に束縛されたターゲットは，シーケンシャル・パターンの次の要素のパターンでパターンマッチされる． 複数の後回しパターン変数が現れた場合，次のシーケンスはそれらをまとめてタプルとしてパターンマッチする．

シーケンシャル・パターンのこの特徴は，パターンの離れた複数の部分についてまとめてnotパターンを適用することを可能にする． たとえば，以下のシーケンシャル・パターンは，ターゲットのコレクションのペアが，共通の要素をちょうど1つだけ含む場合に，パターンマッチに成功する． シーケンシャル・パターンは，それぞれのコレクションに共通の要素があることをチェックした後に，それぞれの残りの要素のコレクションにこれ以上共通要素がないことをチェックすることを可能にする． シーケンシャル・パターンとnotパターンの組み合わせは，数学的なアルゴリズムを記述するときに現れることがある． たとえば，第4章4.1節でも現れる．

def singleCommonElem xs ys := match (xs, ys) as (multiset eq, multiset eq) with
| {($x :: @, #x :: @),
   !($y :: _, #y :: _)} -> True
| _ -> False

シーケンシャル・パターンと同等のことがmatchAll式のネストにより表現できるのではと考えた読者がいるかもしれない． 実は，少なくとも2つの理由でこれは不可能である． 1つ目の理由は，ネストしたmatchAll式は，Egison内部の幅優先探索を壊すことに由来する． 外側のmatchAll式の2番めの結果は，外側のmatchAll式1つ目の結果について内側のmatchAll式の結果をすべて評価した後に計算される． 2つ目の理由は，後回しパターン変数がターゲットだけでなく，マッチャーの情報も保持することである． matchAllの引数のマッチャーが，関数の引数に由来するパラメーターであることがある． それゆえ，内側のmatchAll式で使うべきマッチャーが構文的に導けないことがある．

2.9パターン関数によるパターンのモジュール化

コンス・パターンやジョイン・パターンのようなパターン・コンストラクタは，第6章で解説されるようにマッチャーで定義される． これらのパターン・コンストラクタを組み合わせて，新しいパターン・コンストラクタをつくることができる． そのためには，パターンを引数にとってパターンを返すパターン関数（pattern function）を使う．

パターン関数はdef pattern文で定義する． 名前のあとに，型引数（{a}），型注釈つきの仮引数，そして:に続けて適用結果のパターンが対象とする型を書く． 以下で定義されているパターン関数twinは，それぞれの第一引数が同じ値である場合にマッチするような，二重にネストしたコンス・パターンをモジュール化している． パターン関数の仮引数は変数パターン（variable pattern）と呼ばれる． この例の変数パターンは，pat1とpat2である． 仮引数の型注釈(pat1: a)は，pat1がa型の値にマッチするパターンであることを表す． パターン関数のボディで，変数パターンの中身を参照するときは，~を変数パターンの先頭に付加する． これは変数パターンをパターン・コンストラクタと区別するためである．

def pattern twin {a} (pat1: a) (pat2: [a]) : [a] :=
  (~pat1 & $x) :: #x :: ~pat2

このtwinパターン関数は，以下のように動作する．

match [1, 1, 2, 3] as list integer with
| twin $n $ns -> (n, ns)
-- (1, [2, 3])

パターン関数の型検査については第6章6.12節で解説する．

2.10マッチャー合成による新しいマッチャーの生成

ここまでに登場したマッチャーは，Egison唯一の組み込みマッチャーsomethingを除いて，すべてユーザーが定義することができる． マッチャーを定義するには，第6章で解説するmatcher式を使うことが基本であるが，既存のマッチャーを組み合わせて新しいマッチャーをつくることもできる． この方法で，たとえば，多重集合のタプルのマッチャーや多重集合の多重集合のマッチャーを定義することができる．

タプルに対するマッチャーは，マッチャーのタプルにより表現される． タプル・パターンはそのようなマッチャーを使ったパターンマッチのときに使われる． たとえば，以下は，第1章1.2節でも登場したintersect関数の定義である． 2つの集合のタプルに対するマッチャーを使って，コレクションの共通要素をパターンマッチで取り出している．

def intersect xs ys := matchAll (xs,ys) as (set eq, set eq) with
  | ($x :: _, #x :: _) -> x

上記で使われているeqマッチャーは，同値性が定義されたデータ型eqマッチャーの型は{Eq a} => Matcher aであり，Eq型クラスのインスタンスをもつ型に使える（第6章6.8節）．のパターンマッチに使えるユーザー定義マッチャーである． eqマッチャーに対して，値パターンが使われた場合，同値性のチェックによりパターンマッチがおこなわれる．

また，タプル・マッチャーと，マッチャーを引数にとってマッチャーを返す関数を組み合わせると，さまざまな非自由データ型に対するマッチャーが定義できる． たとえば，グラフの各ノードを整数，グラフの辺を2つのノードのペアとして表現したとき， 有向グラフを表すマッチャーは次のように辺の多重集合として定義できる．

def graph := multiset (integer, integer)

隣接リストにより表現したグラフのマッチャーも定義できる． 隣接リストによるグラフは，整数と整数の多重集合のタプルの多重集合として定義される． ここでも整数によりノードのIDを表現している．

def adjacencyGraph := multiset (integer, multiset integer)

代数的データ型に対するマッチャーはmatcher式によっても定義できるが，代数的データ型に対するマッチャーを簡単な記述で定義できる特別な構文algebraicDataMatcher式をEgisonは提供している． algebraicDataMatcher式は糖衣構文で，matcher式に脱糖される． algebraicDataMatcher式を使えば，たとえば二分木に対するマッチャーは以下のように定義できる．

def binaryTree a := algebraicDataMatcher
  | bLeaf a
  | bNode a (binaryTree a) (binaryTree a)

代数的データ型に対するマッチャーと非自由データ型に対するマッチャーも組み合わせることができる． たとえば，任意の数の子供をもつツリーで子供の順番を無視するマッチャーは以下のように定義できる． 第3章3.4節でこのツリーに対するパターンマッチを紹介する．

def tree a := algebraicDataMatcher
  | leaf a
  | node a (multiset (tree a))