Concurrent Clean : FingerTree

以前からCleanの文字列処理を強化する目論見を持っているのだけれど。
CleanのStringは、Charの配列で、一意型による配列の破壊的更新とあいまって効率的に扱えるのだけれど、文字列のスライスや連結をしようとすると、必ず新しい配列が生成されるので、効率よく取り扱えない。
せっかく更新がない言語なのだから、文字列のスライスをしたときは、もとの文字列への参照を持つようにして、複製をしないようにできるはずなわけで、そのようなライブラリを作りたいと思っていた。
で、String2という型を作って、

:: String2 = String2 !String !Int !Int

という風にして、文字列の始点と終点を持つようなデータ構造を作って、スライスが高速な文字列を作りかけていたのだけれど、文字列の連結はこれでは解決しないので、何かいいデータ構造はないかということをぼんやりと考えていた。
というような時に、ちょうどICFPがあって、FingerTreeというデータ構造が有名になって、おお、これはちょうど欲しいと思っていたやつではないか、ということになったので、しばらくの間FingerTreeで遊ぶことにします。