NLP.Adict.Trie

A (prefix) trie.

Documentation

data Trie a b

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)

A Trie with Maybe values in nodes.

empty :: Ord a => TrieM a b

Empty trie.

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

Insert word with the given value to the trie.

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

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

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

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

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

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

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

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

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

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

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

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