どれちょっとropeをbalancedにoptしてみようか?

http://www.kb.ecei.tohoku.ac.jp/ml2008/program.htm
の

A Functional Implementation of the Garsia-Wachs Algorithm (functional pearl)

がfunctional pearlと書いていて面白そうだったので、ACMのやつとか読めないからO'Browserを諦めてこっちを読んでみました。

www.lri.fr/~filliatr/publis/gw-wml08.pdf <- 元論文
www.kb.ecei.tohoku.ac.jp/ml2008/slides/filliatre.pdf <- ML Workshop 2008のスライド

スライドの方が、ropeに対する応用例としてはちょっと親切です。ICFP2007の遠藤さんとか見えているあたりが。

Garsia-Wachs Algorithmとは?

入力として、非負の重みが付けられた値のlistが与えられた時に、そのlistからある制約を満たすbinary-treeを作る為のアルゴリズムです。
ここでいう制約は、[(treeのrootから、あるleafまでの深さ)*(そのleafの重み)]の総和を最小にせよ、というものです。
イメージとして似た所では、ハフマン符号化なんかがありますが、ちと違うのはこのアルゴリズムが求めるのは、最終的なtreeをin-orderで辿った時の並びが、最初のlistと同じになっているという事です。

コレに関しては、元論文のfig 1.を見てもらった方が明らか。

二つのポイント

この論文では、garsia-wachs algorithmそのものを表す関数garsia_wachsの中で、3つの関数を呼び出しています。
このうち、phase1ではZipperがTree構築の為に使われており、markでは参照型(この論文のコードはOCamlで書かれていますので)が使われています。

感想

相変わらずアメリカ語は意味が分からない。

あと、面白かったのが、Haskellで書こうと思ったら既にHackageにあったっていうw
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/garsia-wachs

STMonadを用いています。

流れとしては、in-orderな時には並ばないけど、コスト最小のtreeを作る->値毎の深さを取る->その深さを元に、in-orderな時に並ぶtreeを作る　で、値毎の深さを取る段階でのみ参照型使っているんですが、別にこれ無くても・・・と思う次第なので、何故使ったのかが多分書かれているでしょうから、それを読み取ったりしないといけないのですが。

##an opportunity to (re)discover ropes, a data structure for long strings
##これとかもそうだなーっていう。実際、あれがないと多分ropeは今現在知らなかったと思いますし。STLPortには入ってるとかw