License	GPL-2
Maintainer	fuuzetsu@fuuzetsu.co.uk
Stability	experimental
Portability	portable
Safe Haskell	None
Language	Haskell2010
Extensions	Cpp TemplateHaskell TemplateHaskellQuotes DeriveGeneric

Data.Trie

Description

An implementation of a trie over a words. Properties:

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

Synopsis

Documentation

A blank Trie

Insert a new string into the trie.

Take a list of String and compress it into a Trie

toList :: Trie -> [String] Source #

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

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

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

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

Instances details

Eq Trie Source #
Instance details Defined in Data.Trie Methods (==) :: Trie -> Trie -> Bool (/=) :: Trie -> Trie -> Bool
Show Trie Source #
Instance details Defined in Data.Trie Methods showsPrec :: Int -> Trie -> ShowS show :: Trie -> String showList :: [Trie] -> ShowS
Generic Trie Source #
Instance details Defined in Data.Trie Associated Types type Rep Trie :: Type -> Type Methods from :: Trie -> Rep Trie x to :: Rep Trie x -> Trie
Binary Trie Source #
Instance details Defined in Data.Trie Methods put :: Trie -> Put get :: Get Trie putList :: [Trie] -> Put
type Rep Trie Source #
Instance details Defined in Data.Trie type Rep Trie = D1 ('MetaData "Trie" "Data.Trie" "word-trie-0.3.0-JIPK5vXawH53KWTtp8vGOv" 'False) (C1 ('MetaCons "Trie" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Bool) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map Char Trie))))

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

Helper function, finds all the suffixes of a given prefix

certainSuffix :: String -> Trie -> String Source #

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