adict-0.3.0: Approximate dictionary searching

Safe HaskellNone

NLP.Adict.Trie

Description

A (prefix) trie.

Synopsis

Documentation

data Trie a b Source

A trie of words with character type a and entry type b. It represents a Map from [a] keys to b values.

Constructors

Trie 

Fields

rootValue :: b

Value in the root node.

edgeMap :: Map a (Trie a b)

Edges to subtries annotated with characters.

Instances

Functor (Trie a) 
(Eq a, Eq b) => Eq (Trie a b) 
(Eq (Trie a b), Ord a, Ord b) => Ord (Trie a b) 
(Show a, Show b) => Show (Trie a b) 
(Ord a, Binary a, Binary b) => Binary (Trie a b) 

type TrieM a b = Trie a (Maybe b)Source

A Trie with Maybe values in nodes.

empty :: Ord a => TrieM a bSource

Empty trie.

insert :: Ord a => [a] -> b -> TrieM a b -> TrieM a bSource

Insert word with the given value to the trie.

fromList :: Ord a => [([a], b)] -> TrieM a bSource

Construct the trie from the list of (word, value) pairs.

toList :: TrieM a b -> [([a], b)]Source

Deconstruct the trie into a list of (word, value) pairs.

follow :: Ord a => [a] -> Trie a b -> Maybe (Trie a b)Source

Follow the path determined by the input word starting in the trie root.

lookup :: Ord a => [a] -> TrieM a b -> Maybe bSource

Search for the value assigned to the given word in the trie.

fromLang :: Ord a => [[a]] -> TrieM a ()Source

Make the trie from the list of words. Annotate each word with the () value.

implicitDAWG :: (Ord a, Ord b) => Trie a b -> Trie a bSource

Elminate common subtries. The result is algebraically a trie but is represented as a DAWG in memory.