Haskellから見るEgisonのパターンマッチング
強力なパターンマッチを備えるというEgisonを触ってみた。シンタックスこそHaskellやOCaml寄りだが、色々と既存の関数型プログラミング言語による先入観に惑わされたので、Haskellと比較する形でメモっておく。
参考にしたのは以下。v4.0.0相当。
パターンの表現力
Egisonにはマッチャーという機構がある。マッチャ―はEgisonのパターンマッチングの根幹をなすが、マッチャーに
list を指定するとHaskellやOCamlで見慣れたリストのパターンマッチと同様のふるまいになるので、まずはわかりやすいところからHaskellのパターンマッチングと比較していきたい。1. パターンマッチングが複数の結果を持てる
この機能はシンプルにわかりやすい一方、これ以降の特徴との強いシナジーがある。
Haskellのパターンマッチは決定的である。パターンマッチは入力にマッチするか否かであり、またマッチした結果はただ一つとなる。
head.hshead xs =
case xs of
x : _ -> x
_ -> 0
head [12, 34, 56] -- => 12
head [] -- => 0もちろんEgisonにおいても同様のパターンマッチを記述できる。
head.egihead xs :=
match xs as list something with -- as ... がマッチャーを指定しているが、後述
| $x :: _ -> x
| _ -> 0
head [12, 34, 56] -- => 12
head [] -- => 0一方、Egisonでは以下のようなパターンも記述できる。
non-head.egiinits xs :=
matchAll xs as list something with
| $xs ++ _ -> xs
inits [12, 34, 56] -- => [[], [12], [12, 34], [12, 34, 56]] $xs ++ _ にはどのようなデータがマッチすると考えられるだろうか? まず任意のリスト ( $xs ) があり、それに続いて ( ++ ) 任意のリスト ( _ ) があればマッチさせることができると考えられる。入力が [12, 34, 56] であれば以下のようなマッチが考えられる。 [] ++ [12, 34, 56] [12] ++ [34, 56] [12, 34] ++ [56] [12, 34, 56] ++ [] matchAll はこのようにマッチする結果全てを列挙する。Egisonの処理系はこのパターンを処理するため内部でバックトラッキングによるパターンマッチングを行う。パターンマッチングが複数の結果を持てることはEgisonの強力な組み込みパターンをより有用にする。以下は
n 個の要素の組合せを列挙する。ここではパターンの入れ子構造を表現できるloopパターンを用いている。combinations.egicombinations xs n :=
matchAllDFS xs as list something with
| loop $i (1, n) (_ ++ $x_i :: ...) _ -> map 1#x_%1 [1..n]ここで
matchAllDFS としているが、これは結果の探索の順序に関与している。 matchAllDFS は文字通り深さ優先探索を行う。2. 非線形なパターン
Egisonのパターンマッチングは「左から右」に行われる。ここで右側のパターンマッチングにおいて左側のパターンマッチングで束縛された変数を参照することができる。以下は入門書でも紹介されている双子素数を列挙するEgisonプログラム。
twin-primes.egitwinPrimes :=
matchAll primes as list integer with
| _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)リスト中のある要素
$p をマッチし、さらにその次の値がp + 2と等しい場合にマッチする。値パターン
#expr のほかに述語パターン ?expr も存在する。 any とか all の定義が以下のようになる。any-and-all.egiany pred xs :=
match xs as list something with
| _ ++ ?pred :: _ -> True
| _ -> False
all pred xs :=
match xs as list something with
| _ ++ !?pred :: _ -> False -- !pat は否定パターン、patにマッチしない場合にマッチする
| _ -> TrueHaskellにはパターンガードがあるが、Haskellのパターンガードは常にパターンにマッチした後の判定になる。この点で1. パターンマッチングが複数の結果を持てることは「左から右」のパターンマッチングと強いシナジーがある。Haskellにおけるリストモナドでの
guard をイメージしてほしい。取り得る候補が莫大になる、「左から右」に多くの分岐を持つ複雑なパターンマッチングにおいても、バックトラッキングによる枝刈りが機能する。以下は入門書で取り上げられている例で、どちらも同じ計算量で [] を返す。backtracking.egimatchAll [1..n] as list integer with
| _ ++ $x :: _ ++ #x :: _ -> x
matchAll [1..n] as list integer with
| _ ++ $x :: _ ++ #x :: _ ++ #x :: _ -> x> Egisonのパターンマッチの特徴は，ユーザーにより拡張可能でかつ，非線形パターン（パターン変数に束縛した値を同じパターン内で参照するパターン）をバックトラッキングにより効率的に処理することである．
3. パターン関数
パターンを引数にとってパターンを返すパターン関数を定義できる。
-> でなく => を用いる。element-at.egi-- n要素目がxであるようなコレクションのパターンを返す関数
elementAt := \n x => loop $i (1, ~n) (_ :: ...) (~x :: _)これはGHC拡張の
PatternSynonyms に似ているが、パターン関数はfirst-class objectなので関数に渡してパターンマッチに使用したり等が可能だ。マッチャー
ここまでEgisonのパターンマッチングの表現力に注視してきたが、Egisonにはマッチャーというパターンマッチの方法そのものを制御する機構がある。
match 式に与えられる as ... がマッチャーの指定にあたる。前提知識: Built-in Data
まず現状、Egisonに静的な型付けはない。ドキュメントの Built-in Data にも
type という単語は出てこない。Egisonのデータには他のプログラミング言語でお馴染みのものも多い。いわゆるアトム的なデータの例:
文字 (
'a' )文字列 (
"string" )ブール値 (
True , False )整数 (
123 )浮動小数点数 (
3.14 )複合データも。
タプル (多値) (
(1, "foo") )コレクション (
[1, 2, 3, 4] )ハッシュマップ (
{| (1, 10), (10, 1) |} )Inductive Data (
Leaf , Node 1 Leaf (Node 2 Leaf Leaf) )最後のInductive Dataには少し驚く。Egisonでは、このようなデータを記述するにあたって事前にユーザーが
data Tree a = Leaf | Node a (Tree a) (Tree a) といった宣言を行う必要はない。あえて既知の関数型言語にイメージを寄せるならOCamlの多相バリアントに近いか...> A variable starting with an upper-case letter is interpreted as a constructor of inductive data. You don’t need to define the inductive data before using it.
それどころか、ユーザー定義のデータ型というもの自体出てこない。これもユーザー定義のマッチャーで表現される。
パターンコンストラクタ
Haskellにおいては、基本的にパターンコンストラクタとそのコンストラクタが示す型は一対一に対応している。パターン中に
: とあるなら、それは基本的にリスト [a] のコンスセルのパターンコンストラクタである。対して、Egisonにおけるconsパターン ( :: ) それ自体は、入力がリストであることを前提としない。マッチャー (list) が、コレクションに対してリストとしてのパターンマッチの方法を与えていると考えられる。matcher.egi-- コレクションをlist somethingとしてマッチする: [(1, [2, 3])] が得られる
matchAll [1, 2, 3] as list something with
| $x :: $xs -> (x, xs)
-- コレクションをmultiset somethingとしてマッチする: [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])] が得られる
matchAll [1, 2, 3] as multiset something with
| $x :: $xs -> (x, xs) multiset マッチャーは、コレクションを多重集合としてパターンマッチする方法を与える。このマッチャーを使えば、例えば n 要素の順列を列挙する関数が以下のように記述できる:permutations.egipermutations xs n :=
matchAllDFS xs as multiset something with
| loop $i (1, n) ($x_i :: ...) _ -> map 1#x_%1 [1..n]マッチャーによってパターンマッチの構文が異なるわけではないことに注意したい。コンス (
:: ) やジョイン ( ++ )、nil ( [] ) 等のパターンコンストラクタの解釈がマッチャーによって与えられる。 permutations の例でも、リストのマッチャーで combinations を定義したときと同様にloopパターンによってn要素の繰り返しを表現している。HaskellでGHC拡張を用いて表現してみるとこんな感じ:
adhoc-pattern.hs{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
-- アドホック多相のための分解(と構築)の型クラスを定義
class MyNil t where
nil :: t a
unNil :: t a -> Maybe ()
class MyCons t where
cons :: a -> t a -> t a
unCons :: t a -> Maybe (a, t a)
-- パターンシノニムでアドホック多相なパターンを定義
pattern Cons :: MyCons t => a -> t a -> t a
pattern Cons x xs <- (unCons -> Just (x, xs))
where Cons x xs = cons x xs
pattern Nil :: MyNil t => t a
pattern Nil <- (unNil -> Just ())
where Nil = nil
instance MyNil [] where
nil = []
unNil [] = Just ()
unNil _ = Nothing
instance MyCons [] where
cons = (:)
unCons (x:xs) = Just (x, xs)
unCons _ = Nothing
-- instance MyNil MultiSet where ...
-- instance MyCons MultiSet where ...
f :: (MyCons t, MyNil t) => Maybe (Integer, t Integer)
f = case Cons 1 (Cons 2 (Cons 3 Nil)) of
Cons x xs -> Just (x, xs)
_ -> Nothingマッチャーは組み込みのマッチャーである
something を除いてすべてユーザーランドで定義されている。Haskellerに身近な例としては maybe マッチャーがある。以下のように利用できる:maybe-matcher.egimatchAll [Just 1, Nothing, Just 2] as multiset (maybe integer) with
| just $x :: _ -> x -- => [1, 2]ここで用いられている
just $x は Inductive patternで、Inductive dataのアナロジーとなっている。パターンコンストラクタは just nothing のように小文字から始まる変数で表現される。 maybe マッチャーの定義は以下の通り:maybe-matcher-definition.egimaybe a := matcher
| nothing as () with
| Nothing -> [()]
| _ -> []
| just $ as (a) with
| Just $x -> [x]
| _ -> []
| $ as (something) with
| $tgt -> [tgt]詳細はドキュメントを参照として、マッチャーの定義は、
1. 原始パターンパターンによる、パターンのパターンマッチ
nothing , just $ , $ がそれぞれに対応する2. 原始データパターンによる、ターゲット(入力)のパターンマッチ
nothing パターンでは、入力が Nothing なら [()] 、それ以外は [] (マッチする結果無し) just $ パターンでは、入力が Just $x なら [x] 、それ以外は [] (マッチする結果無し)....という風に、EgisonのBuilt-in Dataに対するパターンマッチを行う
Haskell等の従来の言語でのパターンマッチに近い
結果がコレクションなのはEgisonのパターンマッチングが複数の結果を持てるため
3. このマッチャーでのデータの分解結果を、子のパターンと
as ... に指定されたマッチャーで再帰的にマッチrec.egi-- 例えば次のような式では
matchAll Just X as maybe Y with
| just Z -> ...
-- Just ($x = X), maybe (a = Y), just ($ = Z) なので、
-- 次の入力は X, 次のマッチャーは Y, 次のパターンは Z
matchAll X as Y with
| Z -> ...特に3番目は難しい。原始データパターンによるデータの分解結果のそれぞれは、原始パターンパターンのパターンホール (
$ ) 数と一致するようなデータ (1要素以外はタプル) でなければならず、また as ... に指定される次のマッチャーも要素数の一致するマッチャー (1要素以外はタプルのマッチャー) でなければならない。 algebraicDataMatcher によって生成されるマッチャーの定義を見ると幾分わかりやすい。term.egiterm := algebraicDataMatcher
| var string
| lam string term
| app term term
-- マッチャ―は以下のように展開されている:
term := matcher
| var $ as string with
| Var $x -> [x]
| _ -> []
| abs $ $ as (string, term) with
| Abs $x $t -> [(x, t)]
| _ -> []
| app $ $ as (term, term) with
| App $s $t -> [(s, t)]
| _ -> []
| $ as something with
| $tgt -> [tgt]
-- 以下のように利用できる:
pretty t :=
match t as term with
| var $x -> x
| lam $x $a -> S.concat ["λ", x, ".", pretty a]
| app $a $b -> S.concat ["(", pretty a, ")", pretty b]パフォーマンス
ユーザー定義のデータ型がない、というところでまず計算量が気になった。特にパターンマッチが一度では済まない再帰的な計算ではどうなるのか? この問いに対する部分的な答えとして
sortedList マッチャーの例がある。例えばあるコレクションに目的の値が含まれるかどうかを判定するには \mathcal{O}(n) かかるが、コレクションがソート済みである前提を設ければ二分探索により \mathcal{O}(\log n) で判定できる。マッチャーの定義においても、入力に前提を設けてパターンマッチを最適化することが考えられる。
以下の式は差が6の素数のペア (セクシー素数) を探索する。
sexy-primes.egitake 10 (matchAll primes as list integer with
| _ ++ $p :: (_ ++ #(p + 6) :: _) -> (p, p + 6))この式では
primes がソート済みのコレクションであるという知識が無いために、検証する必要のない素数のペアを調べ続けるという課題がある。さらに言えば、深さ優先探索 ( matchAllDFS ) では2に対するペアを探し続けて永遠に値が返ってこない。このようなパターンマッチングに sortedList が利用できる。sexy-primes2.egitake 10 (matchAll primes as sortedList integer with
| _ ++ $p :: (_ ++ #(p + 6) :: _) -> (p, p + 6)) sortedList マッチャーは、はソート済みのコレクションを扱う前提において $ ++ #$px :: $ 原始パターンパターンを最適化する。 sorted-list.egisortedList a := matcher
| $ ++ #$px :: $ as (sortedList a, sortedList a) with
| $tgt ->
matchAll tgt as list a with
-- tgtは, [$xa_1, $xa_2, ..., $xa_n, #px, $rs ...] (xa_{1..n} は px より小さい)
-- にマッチしなければならず、素数列に重複はないため、この matchAll は実質的に0か1要素のコレクションになる
-- 例えば上のセクシー素数の列挙において、 p = 5 なら px = 11, tgt = [7, 11, 13, ...] だが、
-- n = 0 では #px と 7 がマッチせず、
-- n = 2 は 11 < px を満たさず、またloopはどんどんネストが深くなるパターンを扱うので
-- これ以上マッチすることはないことがわかり、停止する
| loop $i (1, $n)
((?(< px) & $xa_i) :: ...)
(#px :: $rs) -> (map (\i -> xa_i) [1..n], rs)
...雑感
Egisonで試しにProject Eulerの問題をいくつか解いてみたが、何か気の利いたマッチャーを定義するのはなかなか難しそうだ。慣れてきたらどういう発想でどう記述できるのか...とはいえ、パターンマッチングの表現力はわかりやすく便利そうだ。
例。Problem 11の「格子状のデータから縦/横斜めに
l 個の要素を取り出してその積を求める」といった計算がパターンマッチング一回で記述できて面白い。problem-11.egielementAt := \n x => loop $i (1, ~n) (_ :: ...) (~x :: _)
products l :=
matchAll input as list (list integer) with
| _ ++ (_ ++ (loop $i (1, l) ($n_i :: ...) _)) :: _ -- 横
| _ ++ elementAt $x $n_1 :: (loop $i (2, l) (elementAt #x $n_i :: ...) _) -- 縦
| _ ++ elementAt $x $n_1 :: (loop $i (2, l) (elementAt #(x+i-1) $n_i :: ...) _) -- 斜め (1)
| _ ++ elementAt $x $n_1 :: (loop $i (2, l) (elementAt #(x-i+1) $n_i :: ...) _) -- 斜め (2)
-> product (map 1#n_%1 [1..l])