adict-0.2.0: Approximate dictionary searching

Safe HaskellNone




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

A Trie with Maybe values in nodes.

data Trie a b Source

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




valueIn :: b

Value in the node.

edgeMap :: Map a (Trie a b)

Edges to subtries annotated with characters.


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)])Source

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

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

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

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

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

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

size :: Trie a b -> IntSource

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

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

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

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

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

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

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

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 bSource

FIXME: Null node list case.

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.