F# でHaskellのIntMapを実装してみた
10日ほど前の話ですが、HaskellのIntMapをF#に移植してみました。
移植理由はHaskellのBK-treeが内部でIntMapを利用していたからです。
FSharpxに取り込んでもらっています。
https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Core/DataStructures/IntMap.fs
1日での突貫作業だったのでまだバグがあるかもしれませんが…。
かいつまんだ話
このIntMapはパトリシア木の考えを基に実装されています。大まかな話はWikipediaに書いてあったので、そちらを参照するといいかもしれません。
FSharpxに取り込んでもらうにあたり、テストにFsCheckを併用したので、よかったらそちらの勉強にも参考にどうぞ。
