Data.BKTree

Implementation of a BK-tree: https://en.wikipedia.org/wiki/Bk-tree

Types

type Distance s = s -> s -> Int

data BKTree s

Operations

empty

Arguments

:: Distance s

The distance function "d" must be a metric on "s" (https://en.wikipedia.org/wiki/Metric_space#Definition):

• d x y >= 0
• d x y == 0 iff x == y
• d x y == d y x
• d x z <= d x y + d y z

-> BKTree s

insert :: s -> BKTree s -> BKTree s

query

Arguments

:: Int

The maximum distance to search for.

-> s

-> BKTree s

-> [(s, Int)]

All the words with a distance less than the one specified, and their respective distances.