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

HaskellやScalaでの実装を参考にF# でBKTreeを実装してみた

Scalazの眺めていたら、面白そうなものがあったので自作してみました。
ただし本実装では、Scalazのコードを参考にしているわけではなく、Scalazコード内でコメントに書かれていたHaskellのbktrees-0.3.1ライブラリを参考にしています。

実装したコードはこちらにあります。

BKTreeって?

metric treeの一種です(まるで説明になっていない…)。
下記から順次たどっていけば何がしたいかわかると思うので割愛。

http://en.wikipedia.org/wiki/BK-tree

実行例

実行例はScalazのexampleからお借りしました。

実装例のページにも載せているのですが、こちらにも抜粋しておきます。


実装についてとか

Haskellではtype classとinstance、Scalazではtraitと便利なものがあるようですが、F#にそんなものはないので型ごとにモジュール作っています。
BKTreeクラスを作れば重複を減らすことも可能ですが、クラスにしてもうれしくなかったので作っていません。
速度計測も行っておりませんのであしからず。


あと、string用の実装は行っていないので現状はToCharArrayなどを駆使してchar listにして頑張ってください。
FSharpxのByteStringには対応させようと思っていたのですが力尽きました。体力が回復したら作ると思います。


【10/19追記】
とりあえず程度にByteStringモジュールも作成しました。それに伴い、実行例もByteString版に変更しています。


テストは場当たり的unit test止まりなので、体力が回復したらFsCheckを使ってテストしようと思っています。

作っていた時の感想とか

参照したHaskellのコード、ラムダ式のネストが…私のへなちょこ脳にはきつかったです。でも、理解できる人はあれで理解できるのでしょうね。
あとScalazのコードは難しいけど面白そうなのでScala力あげてリベンジしたいです。