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

LicenseGPL-2
Maintainerfuuzetsu@fuuzetsu.co.uk
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010
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

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 # 

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