Portability | not portable |
---|---|
Stability | experimental |
Maintainer | Uwe Schmidt (uwe@fh-wedel.de) |
Safe Haskell | None |
Facade for prefix tree implementation
- data PrefixTree v
- = Empty
- | Val {
- value' :: v
- tree :: !(PrefixTree v)
- | Branch {
- sym :: !Sym
- child :: !(PrefixTree v)
- next :: !(PrefixTree v)
- | Leaf {
- value' :: v
- | Last {
- sym :: !Sym
- child :: !(PrefixTree v)
- | LsSeq {
- syms :: !Key1
- child :: !(PrefixTree v)
- | BrSeq {
- syms :: !Key1
- child :: !(PrefixTree v)
- next :: !(PrefixTree v)
- | LsSeL { }
- | BrSeL {
- syms :: !Key1
- value' :: v
- next :: !(PrefixTree v)
- | BrVal {
- sym :: !Sym
- value' :: v
- next :: !(PrefixTree v)
- | LsVal { }
- type Key = [Sym]
- (!) :: PrefixTree a -> Key -> a
- value :: Monad m => PrefixTree a -> m a
- valueWithDefault :: a -> PrefixTree a -> a
- null :: PrefixTree a -> Bool
- size :: PrefixTree a -> Int
- member :: Key -> PrefixTree a -> Bool
- lookup :: Monad m => Key -> PrefixTree a -> m a
- findWithDefault :: a -> Key -> PrefixTree a -> a
- prefixFind :: Key -> PrefixTree a -> [a]
- prefixFindWithKey :: Key -> PrefixTree a -> [(Key, a)]
- prefixFindWithKeyBF :: Key -> PrefixTree a -> [(Key, a)]
- empty :: PrefixTree v
- singleton :: Key -> a -> PrefixTree a
- insert :: Key -> a -> PrefixTree a -> PrefixTree a
- insertWith :: (a -> a -> a) -> Key -> a -> PrefixTree a -> PrefixTree a
- insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> PrefixTree a -> PrefixTree a
- delete :: Key -> PrefixTree a -> PrefixTree a
- update :: (a -> Maybe a) -> Key -> PrefixTree a -> PrefixTree a
- updateWithKey :: (Key -> a -> Maybe a) -> Key -> PrefixTree a -> PrefixTree a
- map :: (a -> b) -> PrefixTree a -> PrefixTree b
- mapWithKey :: (Key -> a -> b) -> PrefixTree a -> PrefixTree b
- mapM :: Monad m => (a -> m b) -> PrefixTree a -> m (PrefixTree b)
- mapWithKeyM :: Monad m => (Key -> a -> m b) -> PrefixTree a -> m (PrefixTree b)
- fold :: (a -> b -> b) -> b -> PrefixTree a -> b
- foldWithKey :: (Key -> a -> b -> b) -> b -> PrefixTree a -> b
- union :: PrefixTree a -> PrefixTree a -> PrefixTree a
- unionWith :: (a -> a -> a) -> PrefixTree a -> PrefixTree a -> PrefixTree a
- unionWithKey :: (Key -> a -> a -> a) -> PrefixTree a -> PrefixTree a -> PrefixTree a
- difference :: PrefixTree a -> PrefixTree b -> PrefixTree a
- differenceWith :: (a -> b -> Maybe a) -> PrefixTree a -> PrefixTree b -> PrefixTree a
- differenceWithKey :: (Key -> a -> b -> Maybe a) -> PrefixTree a -> PrefixTree b -> PrefixTree a
- keys :: PrefixTree a -> [Key]
- elems :: PrefixTree a -> [a]
- toList :: PrefixTree a -> [(Key, a)]
- fromList :: [(Key, a)] -> PrefixTree a
- toListBF :: PrefixTree v -> [(Key, v)]
- toMap :: PrefixTree a -> Map Key a
- fromMap :: Map Key a -> PrefixTree a
- space :: PrefixTree a -> Int
- keyChars :: PrefixTree a -> Int
- prefixFindCaseWithKey :: Key -> PrefixTree a -> [(Key, a)]
- prefixFindNoCaseWithKey :: Key -> PrefixTree a -> [(Key, a)]
- prefixFindNoCase :: Key -> PrefixTree a -> [a]
- lookupNoCase :: Key -> PrefixTree a -> [(Key, a)]
- prefixFindCaseWithKeyBF :: Key -> PrefixTree a -> [(Key, a)]
- prefixFindNoCaseWithKeyBF :: Key -> PrefixTree a -> [(Key, a)]
- lookupNoCaseBF :: Key -> PrefixTree a -> [(Key, a)]
Documentation
data PrefixTree v Source
Empty | |
Val | |
| |
Branch | |
| |
Leaf | |
| |
Last | |
| |
LsSeq | |
| |
BrSeq | |
| |
LsSeL | |
BrSeL | |
| |
BrVal | |
| |
LsVal | |
Functor PrefixTree | |
Foldable PrefixTree | |
Eq v => Eq (PrefixTree v) | |
Ord v => Ord (PrefixTree v) | |
Read a => Read (PrefixTree a) | |
Show v => Show (PrefixTree v) | |
Binary a => Binary (PrefixTree a) | |
NFData a => NFData (PrefixTree a) |
(!) :: PrefixTree a -> Key -> aSource
O(min(n,L)) Find the value at a key. Calls error when the element can not be found.
value :: Monad m => PrefixTree a -> m aSource
O(1) Extract the value of a node (if there is one)
valueWithDefault :: a -> PrefixTree a -> aSource
O(1) Extract the value of a node or return a default value if no value exists.
null :: PrefixTree a -> BoolSource
O(1) Is the map empty?
size :: PrefixTree a -> IntSource
O(n) The number of elements.
member :: Key -> PrefixTree a -> BoolSource
O(min(n,L)) Is the key a member of the map?
lookup :: Monad m => Key -> PrefixTree a -> m aSource
O(min(n,L)) Find the value associated with a key. The function will return
the result in
the monad or fail
in it if the key isn't in the map.
findWithDefault :: a -> Key -> PrefixTree a -> aSource
O(min(n,L)) Find the value associated with a key. The function will return
the result in
the monad or fail
in it if the key isn't in the map.
prefixFind :: Key -> PrefixTree a -> [a]Source
O(max(L,R)) Find all values where the string is a prefix of the key.
prefixFindWithKey :: Key -> PrefixTree a -> [(Key, a)]Source
O(max(L,R)) Find all values where the string is a prefix of the key and include the keys in the result.
prefixFindWithKeyBF :: Key -> PrefixTree a -> [(Key, a)]Source
O(max(L,R)) Find all values where the string is a prefix of the key and include the keys in the result. The result list contains short words first
empty :: PrefixTree vSource
singleton :: Key -> a -> PrefixTree aSource
O(1) Create a map with a single element.
insert :: Key -> a -> PrefixTree a -> PrefixTree aSource
O(min(n,L)) Insert a new key and value into the map. If the key is already present in the map, the associated value will be replaced with the new value.
insertWith :: (a -> a -> a) -> Key -> a -> PrefixTree a -> PrefixTree aSource
O(min(n,L)) Insert with a combining function. If the key is already present in the map,
the value of f new_value old_value
will be inserted.
insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> PrefixTree a -> PrefixTree aSource
O(min(n,L)) Insert with a combining function. If the key is already present in the map,
the value of f key new_value old_value
will be inserted.
delete :: Key -> PrefixTree a -> PrefixTree aSource
O(min(n,L)) Delete an element from the map. If no element exists for the key, the map remains unchanged.
update :: (a -> Maybe a) -> Key -> PrefixTree a -> PrefixTree aSource
O(min(n,L)) Updates a value at a given key (if that key is in the trie) or deletes the
element if the result of the updating function is Nothing
. If the key is not found, the trie
is returned unchanged.
updateWithKey :: (Key -> a -> Maybe a) -> Key -> PrefixTree a -> PrefixTree aSource
O(min(n,L)) Updates a value at a given key (if that key is in the trie) or deletes the
element if the result of the updating function is Nothing
. If the key is not found, the trie
is returned unchanged.
map :: (a -> b) -> PrefixTree a -> PrefixTree bSource
O(n) Map a function over all values in the prefix tree.
mapWithKey :: (Key -> a -> b) -> PrefixTree a -> PrefixTree bSource
mapM :: Monad m => (a -> m b) -> PrefixTree a -> m (PrefixTree b)Source
Monadic map
mapWithKeyM :: Monad m => (Key -> a -> m b) -> PrefixTree a -> m (PrefixTree b)Source
Monadic mapWithKey
fold :: (a -> b -> b) -> b -> PrefixTree a -> bSource
O(n) Fold over all values in the map.
foldWithKey :: (Key -> a -> b -> b) -> b -> PrefixTree a -> bSource
O(n) Fold over all key/value pairs in the map.
union :: PrefixTree a -> PrefixTree a -> PrefixTree aSource
unionWith :: (a -> a -> a) -> PrefixTree a -> PrefixTree a -> PrefixTree aSource
O(n+m) Union with a combining function.
unionWithKey :: (Key -> a -> a -> a) -> PrefixTree a -> PrefixTree a -> PrefixTree aSource
O(n+m) Union with a combining function, including the key.
difference :: PrefixTree a -> PrefixTree b -> PrefixTree aSource
(O(min(n,m)) Difference between two tries (based on keys).
differenceWith :: (a -> b -> Maybe a) -> PrefixTree a -> PrefixTree b -> PrefixTree aSource
(O(min(n,m)) Difference with a combining function. If the combining function always returns
Nothing
, this is equal to proper set difference.
differenceWithKey :: (Key -> a -> b -> Maybe a) -> PrefixTree a -> PrefixTree b -> PrefixTree aSource
keys :: PrefixTree a -> [Key]Source
O(n) Returns all values.
elems :: PrefixTree a -> [a]Source
O(n) Returns all values.
toList :: PrefixTree a -> [(Key, a)]Source
O(n) Returns all elements as list of key value pairs,
fromList :: [(Key, a)] -> PrefixTree aSource
O(n) Creates a trie from a list of key/value pairs.
toListBF :: PrefixTree v -> [(Key, v)]Source
returns all key-value pairs in breadth first order (short words first)
this enables prefix search with upper bounds on the size of the result set
e.g. search ... >>> toListBF >>> take 1000
will give the 1000 shortest words
found in the result set and will ignore all long words
toList is derived from the following code found in the net when searching haskell breadth first search
Haskell Standard Libraray Implementation
br :: Tree a -> [a] br t = map rootLabel $ concat $ takeWhile (not . null) $ iterate (concatMap subForest) [t]
toMap :: PrefixTree a -> Map Key aSource
O(n) Convert into an ordinary map.
fromMap :: Map Key a -> PrefixTree aSource
O(n) Convert an ordinary map into a Prefix tree
space :: PrefixTree a -> IntSource
space required by a prefix tree (logically)
Singletons are counted as 0, all other n-ary constructors are counted as n+1 (1 for the constructor and 1 for every field) cons nodes of char lists are counted 2, 1 for the cons, 1 for the char for values only the ref to the value is counted, not the space for the value itself key chars are assumed to be unboxed
keyChars :: PrefixTree a -> IntSource
prefixFindCaseWithKey :: Key -> PrefixTree a -> [(Key, a)]Source
O(max(L,R)) Find all values where the string is a prefix of the key.
prefixFindNoCaseWithKey :: Key -> PrefixTree a -> [(Key, a)]Source
prefixFindNoCase :: Key -> PrefixTree a -> [a]Source
lookupNoCase :: Key -> PrefixTree a -> [(Key, a)]Source
prefixFindCaseWithKeyBF :: Key -> PrefixTree a -> [(Key, a)]Source
O(max(L,R)) Find all values where the string is a prefix of the key. Breadth first variant, short words first in the result list
prefixFindNoCaseWithKeyBF :: Key -> PrefixTree a -> [(Key, a)]Source
lookupNoCaseBF :: Key -> PrefixTree a -> [(Key, a)]Source