RubyにHaskellよりも強力なパターンマッチを実装した

RubyにHaskellなどのような関数型言語のパターンマッチを使っても表現できない強力なパターンマッチを実装しました。
この記事ではその使い方と威力を紹介したいと思います。

ソースコードはGitHubに公開してあります。

(続編 - RubyにHaskellよりも強力なパターンマッチを実装したという記事を新たに書きました。ぜひそちらもご参照ください。)

インストール方法

Gemパッケージとして配布しているため簡単にインストールできます。

$ gem install egison

または

$ gem install bundler (if you need)
$ echo "gem 'egison'" > Gemfile
$ bundle install

使い方

基本的な使い方は以下のとおりです。
本ライブラリをロードすると、match_all構文とmatch構文が使えるようになります。

require 'egison'

include Egison

match_all(object) do
  with(pattern) do
    ...
  end
end

match(object) do
  with(pattern) do
    ...
  end
  with(pattern) do
    ...
  end
  ...
end

パターンマッチに成功すると、withに渡されたブロックが実行され、その結果が返されます。

このライブラリのパターンマッチでは、パターンマッチの結果が複数あるということがあります。
match_all構文はそのすべてのパターンマッチの結果それぞれについてwithに渡されたブロックを実行し、すべての結果をまとめた配列を返します。
match_all構文は1つのwith節を取ります。

一方、matchは複数のwith節を取ります。
先頭のwith節のパターンから順番にパターンマッチに成功するまでパターンマッチを行います。
もしパターンマッチに成功すると、そのwith節に渡されたブロックを実行し、その結果を返します。

色々なパターンを試してみよう

要素パターンと部分コレクションパターン

要素パターンは、ターゲットの配列の要素の1つとパターンマッチします。

部分コレクションパターンは、ターゲットの配列の部分配列とパターンマッチします。
部分コレクションパターンの先頭には*が付きます。

_を先頭に含むリテラルはパターン変数です。
パターンマッチの結果応じて、パターン変数に束縛される値が変わります。

match_all([1, 2, 3]) do
  with(List.(*_hs, _x, *_ts)) do
    [hs, x, ts]
  end
end  #=> [[[],1,[2,3]],[[1],2,[3]],[[1,2],3,[]]

3つのMatcher: List, Multiset, Set

デフォルトの状態ではリスト、多重集合、集合に対してパターンマッチを記述することができます。
多重集合として配列を捉えると、要素の順番が無視されます。
集合として配列を捉えると、要素の順番だけでなく要素の重複も無視されます。

_はワイルドカードです。
ワイルドカードはどのようなオブジェクトともマッチします。
__も___もワイルドカードとして使うことができます。
これは、_と__とがIRBのシステム変数として予約されているためです。

match_all([1, 2, 3]) do
  with(List.(_a, _b, *_)) do
    [a, b]
  end
end  #=> [[1, 2]]

match_all([1, 2, 3]) do
  with(Multiset.(_a, _b, *_)) do
    [a, b]
  end
end  #=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

match_all([1, 2, 3]) do
  with(Set.(_a, _b, *_)) do
    [a, b]
  end
end  #=> [[1, 1],[1, 2],[1, 3],[2, 1],[2, 2],[2, 3],[3, 1],[3, 2],[3, 3]]

_[] が List.() のシンタクスシュガーとして用意されています。

match_all([1, 2, 3]) do
  with(_[_a, _b, *_]) do
    [a, b]
  end
end  #=> [[1, 2]]

非線形パターン

このパターンマッチでは、パターン内で同じ変数が複数回現れるようなパターンを使うことができます。
そのようなパターンは非線形パターン (non-linear pattern) と呼ばれ、既存の関数型言語のパターンマッチでは多くの場合禁止されています。
このパターンを用いると強力なパターンが書けるようになります。

__("...")のような形をしたパターンは値パターンと呼ばれるパターンです。
...の部分に任意のRuby式を書くことができます。
...の部分の式を評価した値とターゲットが同じ値だったらパターンマッチに成功します。

match_all([5, 3, 4, 1, 2]) do
  with(Multiset.(_a, __("a + 1"), __("a + 2"), *_)) do
    a
  end
end  #=> [1,2,3]

値パターンの...の部分に入る式がただの変数の場合、("と")を以下のように省略することができます。

match_all([1, 2, 3, 2, 5]) do
  with(Multiset.(_a, __a, *_)) do
    a
  end
end  #=> [2,2]

デモンストレーション

組み合わせの列挙

パターンマッチを用いてコレクションの要素の組み合わせを列挙することができます。
パターンマッチを用いると何重にもネストするループを記述する必要がなくなります。

require 'egison'

p(match_all([1,2,3,4,5]) do with(List.(*_, _x, *_, _y, *_)) { [x, y] } end)
#=> [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

p(match_all([1,2,3,4,5]) do with(List.(*_, _x, *_, _y, *_, _z, *_)) { [x, y, z] } end)
#=> [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

ポーカーの役判定

すべてのポーカーの役のパターンそれぞれを1つのパターンで記述することができます。
すごいと思いませんか？
HaskellやOCamlのパターンマッチでは以下のように直接パターンマッチですべて記述することはできません。

require 'egison'

def poker_hands cs
  match(cs) do
    with(Multiset.(_[_s, _n], _[__s, __("n+1")], _[__s, __("n+2")], _[__s, __("n+3")], _[__s, __("n+4")])) do
      "Straight flush"
    end
    with(Multiset.(_[_, _n], _[_, __n], _[_, __n], _[_, __n], _)) do
      "Four of kind"
    end
    with(Multiset.(_[_, _m], _[_, __m], _[_, __m], _[_, _n], _[_, __n])) do
      "Full house"
    end
    with(Multiset.(_[_s, _], _[__s, _], _[__s, _], _[__s, _], _[__s, _])) do
      "Flush"
    end
    with(Multiset.(_[_, _n], _[_, __("n+1")], _[_, __("n+2")], _[_, __("n+3")], _[_, __("n+4")])) do
      "Straight"
    end
    with(Multiset.(_[_, _n], _[_, __n], _[_, __n], _, _)) do
      "Three of kind"
    end
    with(Multiset.(_[_, _m], _[_, __m], _[_, _n], _[_, __n], _)) do
      "Two pairs"
    end
    with(Multiset.(_[_, _n], _[_, __n], _, _, _)) do
      "One pair"
    end
    with(Multiset.(_, _, _, _, _)) do
      "Nothing"
    end
  end
end

p(poker_hands([["diamond", 1], ["diamond", 3], ["diamond", 5], ["diamond", 4], ["diamond", 2]])) #=> "Straight flush"
p(poker_hands([["diamond", 1], ["club", 2], ["club", 1], ["heart", 1], ["diamond", 2]])) #=> "Full house"
p(poker_hands([["diamond", 4], ["club", 2], ["club", 5], ["heart", 1], ["diamond", 3]])) #=> "Straight"
p(poker_hands([["diamond", 4], ["club", 10], ["club", 5], ["heart", 1], ["diamond", 3]])) #=> "Nothing"

他にも応用はたくさんあります。

背景

このGemのパターンマッチはプログラミング言語Egisonのパターンマッチを参考にして作られています。
Egisonのパターンマッチは更に強力で、以下の様なこともできます。

• 無限列のパターンマッチ
• 新しいパターンコンストラクタの定義
• パターンのモジュール化

アルゴリズムの記述を本質的に簡潔にする新しい構文の発明というのは本当になかなか現れないもので、このGemのパターンマッチはコンピュータサイエンスの歴史レベルですごいものだと私は思っています。
ぜひ試してみて新しいプログラミングの"感覚"を味わってみてください。

著者について

この記事の著者は現在楽天技術研究所でEgisonの研究・実装を進めたり、
LeoFSというオープンソースの分散オブジェクトストレージの開発に貢献したりするという仕事をしています。