NLP.Adict.Trie

Documentation

type TrieD a b = Trie a (Maybe b)

A Trie with Maybe values in nodes.

data Trie a b

A trie of words with character type a and entry type b. It can be thought of as a map of type [a] -> b.

Constructors

Trie

Fields

valueIn :: b

Value in the 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)

unTrie :: Trie a b -> (b, [(a, Trie a b)])

child :: Ord a => a -> Trie a b -> Maybe (Trie a b)

anyChild :: Trie a b -> [(a, Trie a b)]

mkTrie :: Ord a => b -> [(a, Trie a b)] -> Trie a b

setValue :: b -> Trie a b -> Trie a b

substChild :: Ord a => a -> Trie a b -> Trie a b -> Trie a b

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

size :: Trie a b -> Int

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

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

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

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

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

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

serialize :: (Ord a, Ord b) => Trie a b -> [Node a b]

Serialize the trie and eliminate all common subtries along the way. TODO: perhaps the function name should be different?

deserialize :: Ord a => [Node a b] -> Trie a b

FIXME: Null node list case.

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.