12.87 util.match - パターンマッチング

Module: util.match ¶

このモジュールは Andrew Wright のパターンマッチングマクロライブラリを ポートしたものです。このライブラリは Scheme 界では広くつかわれており、 Chez Scheme、PLT Scheme、Scheme48、Chicken および SLIB を含む、様々な Scheme の実装にポートされています。この機能は Common Lisp の destructuring-bind に似ていますがより強力です。

この版では、オリジナルの Wright’s macro のマクロとの互換性が保たれて います。ただし、例外がふたつあって、それは、(1) box はサポートされて いません。Gauche にそれがないからです。(2) 構造のマッチングは Gauche の オブジェクトシステムに統合されています。

まず API のリストを示し、それからパターンの完全な構文のテーブルを示し、 そして例を示します。

パターンマッチング API

Macro: match expr clause … ¶

{util.match} それぞれの clause は以下のうちどちらかです。

(pat body …)
(pat (=> identifier) body …)

まず、expr を各節の pat に照合します。パターンの詳しい 構文については後述します。

pat にマッチする部分が見つかれば、pat 中の パターン変数 は、expr 中の対応する要素に束縛され、その後、body … が評価されます。matchはbody …の最後の式の値を返します。

節が 2つ目の形式である場合、identifier は clause の失敗継続 に束縛されます。これは引数をもたない手続きで、呼ばれると、あたかも、 pat の照合に失敗したかの如くマッチャーに戻り、match が 残りの節について試行を続けます。それゆえ、body … 内部で 追加のテストを実行することが可能で、もし、満足いくものでなければ、 (identifier) を呼ぶことで、照合結果を拒絶することができます。 より詳しくは、後述の例を見てください。

どの pat もマッチしなければ、match はエラーを報告します。

Macro: match-lambda clause … ¶

{util.match} ひとつの引数をとり、それに対して clause … を用いて、 match を実行する関数を生成します。機能としては以下の式と同等です。

(lambda (expr) (match expr clause …))

例:

(map (match-lambda
       ((item price-per-lb (quantity 'lbs))
        (cons item (* price-per-lb quantity)))
       ((item price-per-lb (quantity 'kg))
        (cons item (* price-per-lb quantity 2.204))))
     '((apple      1.23 (1.1 lbs))
       (orange     0.68 (1.4 lbs))
       (cantaloupe 0.53 (2.1 kg))))
 ⇒ ((apple . 1.353) (orange . 0.952)
            (cantaloupe . 2.4530520000000005))

Macro: match-lambda* clause … ¶

{util.match} match-lambda と同じですが、match をすべての引数のリスト に対して実行します。機能としては以下の式と同等です。

(lambda expr (match expr clause …))

Macro: match-let ((pat expr) …) body-expr … ¶

Macro: match-let name ((pat expr) …) body-expr … ¶

Macro: match-let* ((pat expr) …) body-expr … ¶

Macro: match-letrec ((pat expr) …) body-expr … ¶

{util.match} 束縛部分が単なる変数ではなく、パターンを許す、一般化された let、 let* および letrec です。 各 expr が評価され、その後、pat と照合され、束縛された パターン変数が body-expr … から見えるようになります。

(match-let (
             (((ca . cd) ...)   '((a . 0) (b . 1) (c . 2)))
           )
  (list ca cd))
 ⇒ ((a b c) (0 1 2))

括弧はうんざりという向きには、以下の match-let1 をおためしあれ。

Macro: match-let1 pat expr body-expr … ¶

{util.match} これは Gauche での拡張で、オリジナルの Wright のコードにはありません。 これは以下のコードと同等です。

(match-let ((pat expr)) body-expr …)

構文としては match-let1 は Common Lisp の destructuring-bind に非常によく似ています。

(match-let1 ('let ((var val) ...) body ...)
            '(let ((a b) (c d)) foo bar baz)
  (list var val body))
 ⇒ ((a c) (b d) (foo bar baz))

Macro: match-define pat expr ¶

{util.match} トップレベルの define と同様ですが、変数の代りにパターンが許されます。

(match-define (x . xs) (list 1 2 3))

x  ⇒ 1
xs ⇒ (2 3)

パターンの構文

ここにあるのはパターンの構文の要約です。説明の後にあるアスタリスク (*) はオリジナルの Wright のコードにはない、Gauche の拡張で あることを意味します。

pat : patvar                       ;; 任意のオブジェクトにマッチし、patvarを束縛
    | _                            ;; 任意のオブジェクト
    | ()                           ;; 空リスト
    | #t                           ;; #t
    | #f                           ;; #f
    | string                       ;; 文字列
    | number                       ;; 数
    | character                    ;; 文字
    | keyword                      ;; キーワード (*)
    | 'sexp                        ;; Ｓ式
    | 'symbol                      ;; シンボル(Ｓ式の特殊ケース)
    | (pat1 ... patN)              ;; n 要素のリスト
    | (pat1 ... patN . patN+1)     ;; n 以上の要素を含むリスト
    | (pat1 ... patN patN+1 ooo)   ;; n 以上の要素を含むリスト、残りの各要素は
                                   ;; patN+1 にマッチしなければならない
    | #(pat1 ... patN)             ;; n 要素のベクタ
    | #(pat1 ... patN patN+1 ooo)  ;; n 以上の要素を含むベクタ、残りの各要素は
                                   ;; patN+1 にマッチしなければならない
    | ($ class pat1 ... patN)      ;; オブジェクト (patK はスロット順でマッチ)
    | (struct class pat1 ... patN) ;; 同上 (*)
    | (@ class (slot1 pat1) ...)  ;; オブジェクト (スロット名を使う) (*)
    | (object class (slot1 pat1) ...) ;; 同上 (*)
    | (= proc pat)                 ;; procを適用し、結果を pat にマッチさせる
    | (and pat ...)                ;; すべての pat にマッチするか
    | (or pat ...)                 ;; マッチする pat があるか
    | (not pat ...)                ;; どの pat もマッチしないか
    | (? predicate pat ...)        ;; predicate が真、かつ、全 pat がマッチ
    | (set! patvar)                ;; 任意のオブジェクトにマッチし、セッタを束縛
    | (get! patvar)                ;; 任意のオブジェクトにマッチし、ゲッタを束縛
    | `qp                          ;; 擬似パターン

patvar : a symbol except _, quote, $, struct, @, object, =, and, or,
         not, ?, set!, get!, quasiquote, ..., ___, ..k, __k.

ooo : ...                          ;; ゼロまたはそれ以上
    | ___                          ;; ゼロまたはそれ以上
    | ..k                          ;; k またはそれ以上。kは整数。
                                   ;;   例: ..1, ..2 ...
    | __k                          ;; k またはそれ以上。kは整数。
                                   ;;   例: __1, __2 ...

• 素のシンボルは「パターン変数」で、あらゆるものとマッチし、 式のマッチした部分がそのシンボルに束縛されます。 以下のシンボルは特別な意味をもち、パターン変数としては使えません。 _、quote、$、struct、@、object、 =、and、or、not、?、set!、 get!、quasiquote、...、___ および ..k と __k (ここで、k は整数)。
• シンボル _ はあらゆるものマッチし、パターン変数は束縛しません。 プレースホルダであることを示すのに用います。
• 空リスト、真偽値、文字列、数、文字およびキーワードのリテラルは (equal?という意味で)同じオブジェクトとマッチします。
• クウォートされた式は(equal? という意味で)同じ式とマッチします。 クウォートされたシンボルをそれ自身とマッチさせるのに使えます。
• キーワードは、以前はクオート無しで同じキーワードにマッチしていました。 しかし現在は、キーワードとシンボルの統合に移行中なので、キーワードにマッチさせるために パターンにキーワードを含める際には常にクオートしてください。 詳しくはキーワードとシンボルの統合参照。
• 通常リストおよびベクタは、それぞれ、パターン中の要素にマッチする要素を もつリストまたはベクタとマッチします。ただし、最初の要素が上であげた 特別なシンボルではない限りです。そのような場合には特別な意味を持ちます。

  特別な場合として、ベクタあるいはリストの最後の要素のあとにシンボル ... を付加することができます。この場合には、... シンボル 直前のパターンが与えられた式のすべての要素を尽すまで繰り返し適用されます。 シンボル ___ は ... の場所で使えます。構文規則マクロによって パターンを生成したいときに便利です。

  リストのパターンに対しては、シンボル ..1、..2、… が 使えます。これは繰り返しの最小値を指定するものです。

• ($ class pat1 …) は class クラスのインスタンスと マッチします。各パターン pat1 … はデフォルトではスロットの各値と (class-slots class) の順にマッチします。 (レコードは例外で、0.9.6からデフォルトコンストラクタの順序と同じ順序になりました。)

  (struct class pat1 …) は同じ意味です。オリジナルの Wright のコードには、struct はありませんが、PLT Scheme の拡張 照合機能にはそなわっています。こちらの方がより説明的です。

  これはオリジナルの機能を構造(structure)にもマッチするように調整した ものです。スロットの順番が予め分るような単純なインスタンスをマッチする のに便利です。たとえば、define-record-type (gauche.record - レコード型参照)で作成した 簡単なレコードは簡単に位置指定された値でマッチすることができます。

  インスタンスのクラスが継承を使っている場合、位置によるマッチを おこなうのは少々難しくなります。以下の @ あるいは object パターンを使って、スロット名でマッチを行うことができます。

• (object class (slot1 pat1) …) は slot1 … の値が pat1 … にマッチするような class クラスのインスタンスとマッチします。これは、 Gauche の拡張です。@ は object と同じ場所で使えます。 ただし、object の方が説明的でわかりやすいので、こちらを 推奨します。
• (= proc pat) は最初に proc を対応する式に適用し、 その結果と pat をマッチさせます。
• (and pat …)は、対応する式が全てのpatにマッチした時に マッチに成功します。よく使われるイディオムとして、andで「asマッチング」、 つまり部分式ごとにマッチした全体を別の変数にマッチさせることができます。 例えば(and (x . y) p)はペアにマッチし、そのcarをxに、 cdrをyに、そしてペア全体をpに束縛します。
• (or pat …)は対応する式に対してpatを順に試し、 マッチするものがあればそこで成功、ひとつもマッチしなければ失敗とします。 パターン変数を使う場合、各pat中のパターン変数は同じでなければなりません。 つまり(or (_ x y) (_ x y _)) はokですが、 (or (_ x _) (_ x y _)) は許されません。 マッチするpatによっては束縛されないパターン変数が出てしまうからです。
• (not pat …) はどのpatも式にマッチしない場合に マッチ成功となります。
• (? predicate pat …) は最初、述語を対応する式に適用し、 真が返れば、各 pat … をその式に適用します。
• (set! patvar) はあらゆるものにマッチし、一引数の手続きを パターン変数 patvar に束縛します。その手続きが呼ばれると、 マッチしたパターンの値を与えられた引数で置き換えます。
• (get! patvar) はあらゆるものにマッチし、引数なしの手続きを パターン変数 patvar に束縛します。その手続きが呼ばれると、 マッチしたパターンの値を返します。
• `qpはquasipatternです。qpは、クオートされたパターンと同様、 それそのものにマッチしますが、その中にアンクオートされているパターンがあると、 その部分だけは通常のパターンとして解釈されます。 (準クオート(quasiquote)とquasipatternを混同しないようにしてください。 機能的に両者は似ていますが、準クオートがアンクオートされた部分木以外の 部分の評価をoffにするのに対し、quasipatternはアンクオートされた部分木 以外の部分のパターン構文を無効にします。下の例も参照して下さい。)

パターン例

単純な構造の分解

(match '(0 (1 2) (3 4 5))
  [(a (b c) (d e f))
   (list a b c d e f)])
 ⇒ (0 1 2 3 4 5)

述語パターンの使用

(match 123
  [(? string? x) (list 'string x)]
  [(? number? x) (list 'number x)])
 ⇒ (number 123)

let から変数と式を取り出す 反復および述語パターンの利用

(define let-analyzer
  (match-lambda
    [('let (? symbol?)
           ((var expr) ...)
       body ...)
     (format "named let, vars=~s exprs=~s" var expr)]
    [('let ((var expr) ...)
       body ...)
     (format "normal let, vars=~s exprs=~s" var expr)]
    [_
     (format "malformed let")]))

(let-analyzer '(let ((a b) (c d)) e f g))
 ⇒ "normal let, vars=(a c) exprs=(b d)"

(let-analyzer '(let foo ((x (f a b)) (y (f c d))) e f g))
 ⇒ "named let, vars=(x y) exprs=((f a b) (f c d))"

(let-analyzer '(let (a) b c d))
 ⇒ "malformed let"

= 関数適用。パターン変数 m は正規表現の適用結果にマッチする

(match "gauche-ref.texi"
  ((? string? (= #/(.*)\.([^.]+)$/ m))
   (format "base=~a suffix=~a" (m 1) (m 2))))
 ⇒ "base=gauche-ref suffix=texi"

quasipatternの例です。最初の式では、パターンのうちvalue以外の 部分がクオートされたことになり、従ってシンボルthe, answer, isはパターン変数ではなくリテラルシンボルとなります。 2番目の式がそのことを示しています。入力にあるシンボルwasは パターンのisとマッチしません。もしクオートを行わないと、 全てのシンボルはパターン変数となるので、3番目の例に示すように 任意の4つの要素を持つリストとマッチしてしまいます。

(match '(the answer is 42)
  [`(the answer is ,value) value]
  [_ #f])
 ⇒ 42

(match '(the answer was 42)
  [`(the answer is ,value) value]
  [_ #f])
 ⇒ #f

(match '(a b c d)
  [(the answer is value) value]
  [_ #f])
 ⇒ d

レコードのマッチングの例です。 次のコードは赤黒木をバランスさせる「ローテーション」操作を実装しています。

(define-record-type T #t #t
  color left value right)

(define (rbtree-rotate t)
  (match t
    [(or ($ T 'B ($ T 'R ($ T 'R a x b) y c) z d)
         ($ T 'B ($ T 'R a x ($ T 'R b y c)) z d)
         ($ T 'B a x ($ T 'R ($ T 'R b y c) z d))
         ($ T 'B a x ($ T 'R b y ($ T 'R c z d))))
     (make-T 'R (make-T 'B a x b) y (make-T 'B c z d))]
    [_ t]))