Data.Trie

An implementation of a trie over a words. Properties:

 fromList . toList ≡ id
 toList . fromString ≡ (:[])
 sort . nub . toList . fromList ≡ sort . nub

Documentation

empty :: Trie

A blank Trie

insert :: String -> Trie -> Trie

Insert a new string into the trie.

fromString :: String -> Trie

fromList :: [String] -> Trie

Take a list of String and compress it into a Trie

toList :: Trie -> [String]

Take a trie and expand it into the strings that it represents

lookupPrefix :: MonadPlus m => String -> Trie -> m Trie

Takes a trie and a prefix and returns the sub-trie that of words with that prefix

forcedNext :: Trie -> String

Finds the longest certain path down the trie starting at a the root Invariant Assumption: All paths have at least one true node below them

data Trie

Instances

Eq Trie

Show Trie

Binary Trie

possibleSuffixes :: String -> Trie -> [String]

Helper function, finds all the suffixes of a given prefix

certainSuffix :: String -> Trie -> String

Helper function, finds the longest certain path down the trie starting at a given word