word-trie-0.3.0: Implementation of a finite trie over words.

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

- empty :: Trie
- insert :: String -> Trie -> Trie
- fromString :: String -> Trie
- fromList :: [String] -> Trie
- toList :: Trie -> [String]
- lookupPrefix :: MonadPlus m => String -> Trie -> m Trie
- forcedNext :: Trie -> String
- data Trie
- possibleSuffixes :: String -> Trie -> [String]
- certainSuffix :: String -> Trie -> String

# Documentation

empty :: Trie Source #

A blank Trie

insert :: String -> Trie -> Trie Source #

Insert a new string into the trie.

fromString :: String -> Trie Source #

fromList :: [String] -> Trie Source #

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

forcedNext :: Trie -> String Source #

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 Source #

Instances

Eq Trie Source # |
Methods (==) :: Trie -> Trie -> Bool # (/=) :: Trie -> Trie -> Bool #
Show Trie Source # |
Methods showsPrec :: Int -> Trie -> ShowS # show :: Trie -> String # showList :: [Trie] -> ShowS #
Generic Trie Source # |
Associated Types type Rep Trie :: * -> * # Methods from :: Trie -> Rep Trie x # to :: Rep Trie x -> Trie #
Binary Trie Source # |
Methods put :: Trie -> Put # get :: Get Trie # putList :: [Trie] -> Put #
type Rep Trie Source # |
type Rep Trie = D1 (MetaData "Trie" "Data.Trie" "word-trie-0.3.0-CIZda6nGxva1lEoAMCfGvT" False) (C1 (MetaCons "Trie" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Bool)) (S1 (MetaSel (Nothing 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