読者です 読者をやめる 読者になる 読者になる

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に書いてあったので、そちらを参照するといいかもしれません。

基数木 - Wikipedia

FSharpxに取り込んでもらうにあたり、テストにFsCheckを併用したので、よかったらそちらの勉強にも参考にどうぞ。