bk-tree-0.1.1: BK-tree implementation

Safe HaskellSafe-Inferred

Data.BKTree

Contents

Description

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

Synopsis

Types

type Distance s = s -> s -> IntSource

data BKTree s Source

Operations

emptySource

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 sSource

querySource

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.