Ruby向けパターンマッチライブラリ「pattern-match」を作った

2012-03-03 (Sat)

))) Ruby向けパターンマッチライブラリ「pattern-match」を作った

先日ポストしたScalaっぽいパターンマッチをRubyで実装するをベースに一通り機能を揃えてライブラリ化した(pattern-match)。

面白そうなパターンをいくつか例に取ってみると、まず多重代入。

match([0, [1, 2, 3, 4]]) {
  with(_[a, _[b, *c, d]]) { # `Array.(a, Array.(b, *c, d))'と同じ
    p [a, b, c, d] #=> [0, 1, [2, 3], 4]
  }
}

Gaucheのutil.match由来の___、__k。

match([[0, 1], [2, 3]]) {
  with(_[_[a, b], ___]) {
    p [a, b] #=> [[0, 2], [1, 3]]
  }
}

赤黒木のbalance(参考までにScala版実装)。

Node = Struct.new(:left, :key, :right)
class R < Node; end
class B < Node; end

def balance(left, key, right)
  match([left, key, right]) {
    with(_[R.(a, x, b), y, R.(c, z, d)]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R.(R.(a, x, b), y, c), z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R.(a, x, R.(b, y, c)), z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R.(b, y, R.(c, z, d))]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R.(R.(b, y, c), z, d)]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_) { B[left, key, right] }
  }
end

特殊なパターンとしてDuck Typing的なことも出来るようにしてみた。ただ、実用性があるかというと、どうなんだろう……。

match(10) {
  with(Object.(:to_i => a, :foobar => b)) { :not_match }
  with(Object.(:to_i => a, :to_s.(16) => b)) {
    p [a, b] #=> [10, "a"]
  }
}

ちなみに、ruby-trunk - Feature #4085 : Refinements and nested methodsをサポートする環境であれば、次のような書き方も出来るようになっている*1。Refinements素晴らしい。

def balance(left, key, right)
  match([left, key, right]) {
    with(_[R[a, x, b], y, R[c, z, d]]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R[R[a, x, b], y, c], z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R[a, x, R[b, y, c]], z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R[b, y, R[c, z, d]]]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R[R[b, y, c], z, d]]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_) { B[left, key, right] }
  }
end

*1 r29944向けパッチで動作確認済み

本日のツッコミ(全5件) [ツッコミを入れる]

_ shugo (2012-03-07 (Wed) 23:47)

赤黒木のdeleteを実装して気付いたのですが、matchがネストすると外側のパターンマッチで得た変数(実際はメソッド)を内側で参照できないようです。 あと、以下のコードではなぜかundefined local variable or method `x'になってしまいました。RedNode[app(a, b), x, xv, c]の部分を別メソッドにすると大丈夫でした。 with _[a, RedNode.(b, x, xv, c)] do RedNode[app(a, b), x, xv, c] end 参考: https://gist.github.com/1993507

_ k_tsj (2012-03-08 (Thu) 22:37)

> matchがネストすると外側のパターンマッチで得た変数(実際はメソッド)を内側で参照できないようです。 外側で得た変数を内側のwithの引数として渡しても、値の参照ではなく常にvariable pattern相当になってしまうということですよね。 最終的にはこれらの変数はレキシカルスコープなものにしたいと思っていますが、 まだ方法を考え中のため簡易実装でお茶を濁しているのが現状です。 修正されるまでの間は、一旦ローカル変数に代入してそちらを使うようにするといった逃げ方をしてもらう必要があります。 > 以下のコードではなぜかundefined local variable or method `x'になってしまいました。 使っているRubyのバージョンを教えていただけないでしょうか。 以下のコードで再現を試みましたが、 ruby -e 'load "red_black.rb"' -e ' def app(*); end match([0, RedBlack::RedNode[1, 2, 3, 4]]) do with _[a, ::RedBlack::RedNode.(b, x, xv, c)] do RedBlack::RedNode[app(a, b), x, xv, c] end end ' 次のいずれのバージョンでもエラーとなりませんでした。 ruby 1.9.2p290 (2011-07-09) [x86_64-linux] ruby 1.9.3p125 (2012-02-16 revision 34643) [x86_64-linux] ruby 2.0.0dev (2012-03-08 trunk 34947) [x86_64-linux]

_ shugo (2012-03-09 (Fri) 11:35)

> 外側で得た変数を内側のwithの引数として渡しても、値の参照ではなく常にvariable pattern相当になってしまうということですよね。 いえ、 withの引数ではなくブロック内で参照してもエラーになったのですが、matchのネストは関係なくて、もう一つのエラーと同根かもしれません。 > 次のいずれのバージョンでもエラーとなりませんでした。 バージョンはruby 2.0.0dev (2012-02-26 trunk 34819) [i686-linux]ですが、単純なケースでは再現しないかもしれません。 以下のコードだと再現します。 https://gist.github.com/2004685 169行目のif falseをif trueにしてRedNode[app(a, b), x, xv, c]を 別のメソッドで実行するようにすればエラーが出なくなります。

_ k_tsj (2012-03-10 (Sat) 09:56)

なるほど、分かりました。 やはり両方ともmatchのネストが原因のようです。 GitHub上のmasterに修正をコミットしておきました。 red_black_error.rbが通ることは確認済みです。

_ shugo (2012-03-14 (Wed) 11:28)

ありがとうございました。後で確認してみます

継続にっき

2012-03-03 (Sat)

))) Ruby向けパターンマッチライブラリ「pattern-match」を作った