Language.Distance.Search

The Search typeclass lets you build dictinaries and then query them to find words close to a given one.

Right now two data types are provided: TST and BK, monomorphic functions are provided as well. The difference is in performance: TST is faster for low distances (less than 3) but impractical for larger ones, where BK is more suited. See the specific modules for more info.

Documentation

class Search container full algo | container -> full, container -> algo where

Generic class for data structures that can perform queries retrieving words close to a given one.

Minimal definition: empty, insert, and query.

Methods

empty :: container

insert :: full -> container -> container

query

Arguments

:: Int

The maximum distance to search for

-> full

The starting word

-> container

-> [(full, Distance algo)]

singleton :: full -> container

member :: full -> container -> Bool

fromList :: [full] -> container

Instances

(Eq sym, ListLike full sym, EditDistance sym algo) => Search (BKDist full sym algo) full algo

(Ord sym, ListLike full sym, EditDistance sym DamerauLevenshtein) => Search (TSTDist full sym DamerauLevenshtein) full DamerauLevenshtein

(Ord sym, ListLike full sym, EditDistance sym Levenshtein) => Search (TSTDist full sym Levenshtein) full Levenshtein

newtype TSTDist full sym algo

We need to wrap TSTSet in a newtype because we need the algorithm and the container have to depend on the type.

Constructors

TSTDist

Fields

getTST :: TSTSet sym

Instances

(Ord sym, ListLike full sym, EditDistance sym DamerauLevenshtein) => Search (TSTDist full sym DamerauLevenshtein) full DamerauLevenshtein

(Ord sym, ListLike full sym, EditDistance sym Levenshtein) => Search (TSTDist full sym Levenshtein) full Levenshtein

newtype BKDist full sym algo

Again, wrapping BKTree to have the phantom types in place.

Constructors

BKDist

Fields

getBK :: BKTree full algo

Instances

(Eq sym, ListLike full sym, EditDistance sym algo) => Search (BKDist full sym algo) full algo