Haskellから見るEgisonのパターンマッチング

強力なパターンマッチを備えるというEgisonを触ってみた。シンタックスこそHaskellやOCaml寄りだが、色々と既存の関数型プログラミング言語による先入観に惑わされたので、Haskellと比較する形でメモっておく。

参考にしたのは以下。v4.0.0相当。

最近(2020/05/01)出てた入門書(PDF)

/icons/hr.icon

パターンの表現力

Egisonにはマッチャーという機構がある。マッチャ―はEgisonのパターンマッチングの根幹をなすが、マッチャーに list を指定するとHaskellやOCamlで見慣れたリストのパターンマッチと同様のふるまいになるので、まずはわかりやすいところからHaskellのパターンマッチングと比較していきたい。

1. パターンマッチングが複数の結果を持てる

この機能はシンプルにわかりやすい一方、これ以降の特徴との強いシナジーがある。

Haskellのパターンマッチは決定的である。パターンマッチは入力にマッチするか否かであり、またマッチした結果はただ一つとなる。

code:head.hs

head xs =

case xs of

x : _ -> x

_ -> 0

head 12, 34, 56 -- => 12

head [] -- => 0

もちろんEgisonにおいても同様のパターンマッチを記述できる。

code:head.egi

head xs :=

match xs as list something with -- as ... がマッチャーを指定しているが、後述

| $x :: _ -> x

| _ -> 0

head 12, 34, 56 -- => 12

head [] -- => 0

一方、Egisonでは以下のようなパターンも記述できる。

code:non-head.egi

inits 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パターンを用いている。

code:combinations.egi

combinations 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プログラム。

code:twin-primes.egi

twinPrimes :=

matchAll primes as list integer with

| _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)

リスト中のある要素 $p をマッチし、さらにその次の値がp + 2と等しい場合にマッチする。

値パターン #expr のほかに述語パターン ?expr も存在する。 any とか all の定義が以下のようになる。

code:any-and-all.egi

any pred xs :=

match xs as list something with

| _ ++ ?pred :: _ -> True

| _ -> False

all pred xs :=

match xs as list something with

| _ ++ !?pred :: _ -> False -- !pat は否定パターン、patにマッチしない場合にマッチする

| _ -> True

Haskellにはパターンガードがあるが、Haskellのパターンガードは常にパターンにマッチした後の判定になる。この点で1. パターンマッチングが複数の結果を持てることは「左から右」のパターンマッチングと強いシナジーがある。Haskellにおけるリストモナドでの guard をイメージしてほしい。取り得る候補が莫大になる、「左から右」に多くの分岐を持つ複雑なパターンマッチングにおいても、バックトラッキングによる枝刈りが機能する。以下は入門書で取り上げられている例で、どちらも同じ計算量で [] を返す。

code:backtracking.egi

matchAll 1..n as list integer with

| _ ++ $x :: _ ++ #x :: _ -> x

matchAll 1..n as list integer with

| _ ++ $x :: _ ++ #x :: _ ++ #x :: _ -> x

Egisonのパターンマッチの特徴は，ユーザーにより拡張可能でかつ，非線形パターン（パターン変数に束縛した値を同じパターン内で参照するパターン）をバックトラッキングにより効率的に処理することである．

3. パターン関数

パターンを引数にとってパターンを返すパターン関数を定義できる。 -> でなく => を用いる。

code:element-at.egi

-- n要素目がxであるようなコレクションのパターンを返す関数

elementAt := \n x => loop $i (1, ~n) (_ :: ...) (~x :: _)

これはGHC拡張の PatternSynonyms に似ているが、パターン関数はfirst-class objectなので関数に渡してパターンマッチに使用したり等が可能だ。

/icons/hr.icon

マッチャー

ここまで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) が、コレクションに対してリストとしてのパターンマッチの方法を与えていると考えられる。

code: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 要素の順列を列挙する関数が以下のように記述できる:

code:permutations.egi

permutations 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拡張を用いて表現してみるとこんな感じ:

code: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 マッチャーがある。以下のように利用できる:

code:maybe-matcher.egi

matchAll Just 1, Nothing, Just 2 as multiset (maybe integer) with

| just $x :: _ -> x -- => 1, 2

ここで用いられている just $x は Inductive patternで、Inductive dataのアナロジーとなっている。パターンコンストラクタは just nothing のように小文字から始まる変数で表現される。

maybe マッチャーの定義は以下の通り:

code:maybe-matcher-definition.egi

maybe 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 ... に指定されたマッチャーで再帰的にマッチ

code: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 によって生成されるマッチャーの定義を見ると幾分わかりやすい。

code:term.egi

term := 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

他、 lib/core/collection.egi に list や multiset といったマッチャーの定義があるので見てみるとよいだろう。

パフォーマンス

ユーザー定義のデータ型がない、というところでまず計算量が気になった。特にパターンマッチが一度では済まない再帰的な計算ではどうなるのか? この問いに対する部分的な答えとして sortedList マッチャーの例がある。

例えばあるコレクションに目的の値が含まれるかどうかを判定するには $ \mathcal{O}(n) かかるが、コレクションがソート済みである前提を設ければ二分探索により $ \mathcal{O}(\log n) で判定できる。マッチャーの定義においても、入力に前提を設けてパターンマッチを最適化することが考えられる。

以下の式は差が6の素数のペア (セクシー素数) を探索する。

code:sexy-primes.egi

take 10 (matchAll primes as list integer with

| _ ++ $p :: (_ ++ #(p + 6) :: _) -> (p, p + 6))

この式では primes がソート済みのコレクションであるという知識が無いために、検証する必要のない素数のペアを調べ続けるという課題がある。さらに言えば、深さ優先探索 (matchAllDFS) では2に対するペアを探し続けて永遠に値が返ってこない。このようなパターンマッチングに sortedList が利用できる。

code:sexy-primes2.egi

take 10 (matchAll primes as sortedList integer with

| _ ++ $p :: (_ ++ #(p + 6) :: _) -> (p, p + 6))

sortedList マッチャーは、はソート済みのコレクションを扱う前提において $ ++ #$px :: $ 原始パターンパターンを最適化する。

code:sorted-list.egi

sortedList 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)

...

/icons/hr.icon

雑感

Egisonで試しにProject Eulerの問題をいくつか解いてみたが、何か気の利いたマッチャーを定義するのはなかなか難しそうだ。慣れてきたらどういう発想でどう記述できるのか...とはいえ、パターンマッチングの表現力はわかりやすく便利そうだ。

例。Problem 11の「格子状のデータから縦/横斜めに l 個の要素を取り出してその積を求める」といった計算がパターンマッチング一回で記述できて面白い。

code:problem-11.egi

elementAt := \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)