Route 477

■ [ruby] RubyでZipperを実装してみた

Zipperについては

• http://www.kmonos.net/wlog/55.php#_2114051118

を見てほしいのですが、簡単に言うと副作用を使わずに実装された双方向リストみたいな感じです。

例。

# zipperを作る
zipper = Zipper.make(1, 2, 3)
# 最初は、0番目にカーソルがある
zipper.get   #=> 1
# nextを呼ぶと、1番目にカーソルが移動する
zipper.next.get  #=> 2

んで書き換えもできるのですが、「副作用なし」なので、書き換えると丸ごと別のzipperができます。

orig = Zipper.make(1, 2, 3)
copy1 = orig.next.set(100)
copy2 = orig.next.set(200)

copy1.to_a   #=> [1, 100, 3]
copy2.to_a   #=> [1, 200, 3]

「なんだか遅そう」って？それがO(1)、つまりどんなに長くなっても同じ時間で行えるのがZipperの凄いところなんです。

試しにこんなテストを書いてみました。

 it "Zipperは、大量にコピーしてそれぞれ書き換えたりしてもへっちゃら！" do
   original = Zipper.make(*(0..10000).to_a)   # 長さ10000のzipperを作って、
   zippers = (0..10000).map{|i|               # それを10000個、
     original.next.set(i)                     # 1箇所ずつ書き換えて複製する
   }
   zippers[99].get.should == 99
   zippers[1234].get.should == 1234
 end

二次元配列でこれをやると10000 * 10000なので凄い時間がかかりそうですが、Zipperでは0.5秒で終わります(僕のMacBook調べ)。

まあ、Rubyのライブラリとして何に使えるかというと、ぱっと思いつかないのですが(笑)、なかなか面白かったです。

ソースは最近話題の(って遅いけど) gist にアップロードしてみました。間違ってゲストで投稿しちゃったんだけど、その場でログインしたらownerがyharaになるとか気が利いてますね。

• http://gist.github.com/4357