HaskellやScalaでの実装を参考にF# でBKTreeを実装してみた
Scalazの眺めていたら、面白そうなものがあったので自作してみました。
ただし本実装では、Scalazのコードを参考にしているわけではなく、Scalazコード内でコメントに書かれていたHaskellのbktrees-0.3.1ライブラリを参考にしています。
実装したコードはこちらにあります。
BKTreeって？
metric treeの一種です（まるで説明になっていない…）。
下記から順次たどっていけば何がしたいかわかると思うので割愛。
実行例
実行例はScalazのexampleからお借りしました。
実装例のページにも載せているのですが、こちらにも抜粋しておきます。
実装についてとか
Haskellではtype classとinstance、Scalazではtraitと便利なものがあるようですが、F#にそんなものはないので型ごとにモジュール作っています。
BKTreeクラスを作れば重複を減らすことも可能ですが、クラスにしてもうれしくなかったので作っていません。
速度計測も行っておりませんのであしからず。
あと、string用の実装は行っていないので現状はToCharArrayなどを駆使してchar listにして頑張ってください。
FSharpxのByteStringには対応させようと思っていたのですが力尽きました。体力が回復したら作ると思います。
【10/19追記】
とりあえず程度にByteStringモジュールも作成しました。それに伴い、実行例もByteString版に変更しています。
テストは場当たり的unit test止まりなので、体力が回復したらFsCheckを使ってテストしようと思っています。
