miura1729の日記

パターンマッチの続き

19:08 |

まめめもでku-ma-meさんがパターンマッチを使って面白そうなことをしておられるので、私もやってみました。

http://d.hatena.ne.jp/ku-ma-me/20100522/p1

やっぱり実践的な使い方をするといろいろ問題点が出てきて良いですね。最新版のプログラム(matcher.rb)です。　http://gist.github.com/372413

足し算をやってみました。

require 'matcher.rb'

mat = Matcher.new
mat.pattern([Quote::quote(:Sum), :left, :right]) {|hash|
  mat.match(hash[:left]) + mat.match(hash[:right])
}
mat.pattern([Quote::quote(:Const), :value]) {|hash|
  hash[:value]
}

p mat.match([:Sum, [:Sum, [:Const, 1], [:Const, 2]], 
                   [:Sum, [:Const, 3], [:Const, 4]]])

赤黒木です。一度パターンをコンパイルしたら次回からコンパイルしないでコンパイル済みのコードを再利用しているのですが、赤黒木の例ではパーターンマッチ後の動作を定義するブロック(クロージャ)で外の環境のローカル変数を参照しているのでうまく再利用が効きません。そのためとても効率が悪いです。クロージャをちゃんと更新するようにするのが今後の課題です。

require 'matcher'

module RedBlackTree
  include Quote

  def insert(x, t)
    a = insert0(x, t)
    a = a.dup
    a[0] = :B
    a
  end

  def insert0(x, t)
    inspat = Matcher.new
    inspat.pattern([]) {|hash|
      [:R, [], x, []]
    }

    inspat.pattern([quote(:B), :a, :y, :b]) {|hash|
      case
      when x < hash[:y]; balance(insert0(x, hash[:a]), hash[:y], hash[:b])
      when x > hash[:y]; balance(hash[:a], hash[:y], insert0(x, hash[:b]))
      else t
      end
    }

    inspat.pattern([quote(:R), :a, :y, :b]) {|hash|
      case
      when x < hash[:y]; [:R, insert0(x, hash[:a]), hash[:y], hash[:b]]
      when x > hash[:y]; [:R, hash[:a], hash[:y], insert0(x, hash[:b])]
      else t
      end
    }

    inspat.match(t)
  end
  
  def member(x, t)
    mempat = Matcher.new
    mempat.pattern([[Symbol, :col], :a, :y, :b]) {|hash|
      case
        when x<hash[:y]; member(x, hash[:a])
        when x>hash[:y]; member(x, hash[:b])
        else true
      end
    }

    mempat.pattern([:dmy]) {|hash|
      false
    }

    mempat.match(t)
  end


  def balance(l, v, r)
    balpat = Matcher.new
    matexc = lambda {|hash|
      [:R, 
       [:B, hash[:a], hash[:x], hash[:b]], 
       hash[:y],
       [:B, hash[:c], hash[:z], hash[:d]]]
    }
    balpat.pattern([[quote(:R), [quote(:R), :a, :x, :b], :y, :c], :z, :d], &matexc)
    balpat.pattern([[quote(:R), :a, :x, [quote(:R), :b, :y, :c]], :z, :d], &matexc)
    balpat.pattern([[quote(:R), :a, :x, :b], :y, [quote(:R), :c, :z, :d]], &matexc)
    balpat.pattern([:a, :x, [quote(:R), [quote(:R), :b, :y, :c], :z, :d]], &matexc)
    balpat.pattern([:a, :x, [quote(:R), :b, :y, [quote(:R), :c, :z, :d]]], &matexc)
    balpat.pattern([:a, :x, :b]) {|hash|
      [:B, hash[:a], hash[:x], hash[:b]]
    }

    balpat.match([l, v, r])
  end
end

include RedBlackTree
tree = []
(1..10).to_a.shuffle.each do |x|
  tree = insert(x, tree)
end

p member( 5, tree) #=> true
p member(11, tree) #=> false
p member( 0, tree) #=> false
p tree