Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Trie
Portabilityunknown This module provides a basic implementation of the Trie data type.
Stabilityvolatile
Maintainerjeanphilippe.bernardy; google mail.
Contents
Data type
Operators
Query
Construction
Insertion
Delete/Update
Combine
Union
Difference
Intersection
Traversal
Map
Fold
Conversion
Filter
Submap
Primitive accessors
Derived operations
Debugging
Description
Note: performance is currently rather bad. See the benchmark directory. Please contribute :)
Synopsis
data Trie s k v = Trie {
value :: !(Maybe v)
children :: !(Map k (Trie s k v))
}
(!) :: forall s k v . (Foldable s k, Ord k) => Trie s k v -> s -> v
null :: Trie s k v -> Bool
member :: forall s k v . (Foldable s k, Ord k) => s -> Trie s k v -> Bool
lookup :: forall s m k v . (Foldable s k, Monad m, Ord k) => s -> Trie s k v -> m v
prefixLookup :: forall s k v result . (Ord k, Sequence s k, Sequence result (s, v)) => s -> Trie s k v -> result
empty :: Ord k => Trie s k v
singleton :: (Ord k, Foldable s k) => s -> v -> Trie s k v
insert :: forall s k v . (Foldable s k, Ord k) => s -> v -> Trie s k v -> Trie s k v
insertWith :: forall s k v . (Foldable s k, Ord k) => (v -> v -> v) -> s -> v -> Trie s k v -> Trie s k v
alter :: forall s k v . (Foldable s k, Ord k) => (Maybe v -> Maybe v) -> s -> Trie s k v -> Trie s k v
union :: Ord k => Trie s k v -> Trie s k v -> Trie s k v
unionWith :: Ord k => (v -> v -> v) -> Trie s k v -> Trie s k v -> Trie s k v
difference :: Ord k => Trie s k v -> Trie s k v -> Trie s k v
differenceWith :: Ord k => (v -> v -> Maybe v) -> Trie s k v -> Trie s k v -> Trie s k v
intersection :: Ord k => Trie s k v -> Trie s k v -> Trie s k v
intersectionWith :: Ord k => (v -> v -> v) -> Trie s k v -> Trie s k v -> Trie s k v
retypeKeys :: Trie s1 k v -> Trie s2 k v
fromAscList :: forall s k v . (Sequence s k, Ord k) => [(s, v)] -> Trie s k v
fromList :: forall s k v . (Sequence s k, Ord k) => [(s, v)] -> Trie s k v
fromListWith :: forall s k v . (Sequence s k, Ord k) => (v -> v -> v) -> [(s, v)] -> Trie s k v
toList :: (Sequence s k, Ord k) => Trie s k v -> [(s, v)]
filter :: forall k v s . (Ord k, Sequence s k) => (v -> Bool) -> Trie s k v -> Trie s k v
isSubmapOfBy :: Ord k => (v -> v -> Bool) -> Trie s k v -> Trie s k v -> Bool
upwards :: Ord k => (Trie s k v -> Trie s k v) -> Trie s k v -> Trie s k v
downwards :: Ord k => (Trie s k v -> Trie s k v) -> Trie s k v -> Trie s k v
takeWhile :: Ord k => (Trie s k v -> Bool) -> Trie s k v -> Trie s k v
takeWhile' :: Ord k => (v -> Bool) -> Trie s k v -> Trie s k v
fringe :: Ord k => Trie s k v -> Trie s k v
toTree :: k -> Trie s k v -> Tree (k, Maybe v)
Data type
data Trie s k v
A Trie with key elements of type k (keys of type [k]) and values of type v. Note that the type is not opaque: user can pattern match on it and construct and Trie value. This is because there is no non-trivial invariant to preserve.
Constructors
Trie
value :: !(Maybe v)
children :: !(Map k (Trie s k v))
show/hide Instances
Typeable3 Trie
Foldable (Trie s k)
(Eq k, Eq v) => Eq (Trie s k v)
Ord k => Monoid (Trie s k v)
(Show k, Show v) => Show (Trie [k] k v)
Sequence s k => Foldable (Trie s k v) (s, v)
(Ord k, Sequence s k) => Collection (Trie s k v) (s, v) (s, v)
(Ord k, Foldable s k) => Indexed (Trie s k v) s v
(Ord k, Sequence s k) => Map (Trie s k v) s v
Operators
(!) :: forall s k v . (Foldable s k, Ord k) => Trie s k v -> s -> v
Query
null :: Trie s k v -> Bool
Is the trie empty ?
member :: forall s k v . (Foldable s k, Ord k) => s -> Trie s k v -> Bool
lookup :: forall s m k v . (Foldable s k, Monad m, Ord k) => s -> Trie s k v -> m v
prefixLookup :: forall s k v result . (Ord k, Sequence s k, Sequence result (s, v)) => s -> Trie s k v -> result
prefixLookup k p returns a sequence of all (k',v) pairs, such that k is a prefix of k'. The sequence is sorted by lexicographic order of keys.
Construction
empty :: Ord k => Trie s k v
The empty trie.
singleton :: (Ord k, Foldable s k) => s -> v -> Trie s k v
The singleton trie.
Insertion
insert :: forall s k v . (Foldable s k, Ord k) => s -> v -> Trie s k v -> Trie s k v
insertWith :: forall s k v . (Foldable s k, Ord k) => (v -> v -> v) -> s -> v -> Trie s k v -> Trie s k v
Delete/Update
alter :: forall s k v . (Foldable s k, Ord k) => (Maybe v -> Maybe v) -> s -> Trie s k v -> Trie s k v
Combine
Union
union :: Ord k => Trie s k v -> Trie s k v -> Trie s k v
Combining two tries. The first shadows the second.
unionWith :: Ord k => (v -> v -> v) -> Trie s k v -> Trie s k v -> Trie s k v
Combining two tries. If the two define the same key, the specified combining function is used.
Difference
difference :: Ord k => Trie s k v -> Trie s k v -> Trie s k v
differenceWith :: Ord k => (v -> v -> Maybe v) -> Trie s k v -> Trie s k v -> Trie s k v
Intersection
intersection :: Ord k => Trie s k v -> Trie s k v -> Trie s k v
intersectionWith :: Ord k => (v -> v -> v) -> Trie s k v -> Trie s k v -> Trie s k v
Combining two tries. If the two tries define the same key, the specified combining function is used.
Traversal
Map
Fold
Conversion
retypeKeys :: Trie s1 k v -> Trie s2 k v
fromAscList :: forall s k v . (Sequence s k, Ord k) => [(s, v)] -> Trie s k v
fromList :: forall s k v . (Sequence s k, Ord k) => [(s, v)] -> Trie s k v
fromListWith :: forall s k v . (Sequence s k, Ord k) => (v -> v -> v) -> [(s, v)] -> Trie s k v
toList :: (Sequence s k, Ord k) => Trie s k v -> [(s, v)]
Filter
filter :: forall k v s . (Ord k, Sequence s k) => (v -> Bool) -> Trie s k v -> Trie s k v
Submap
isSubmapOfBy :: Ord k => (v -> v -> Bool) -> Trie s k v -> Trie s k v -> Bool
Primitive accessors
upwards :: Ord k => (Trie s k v -> Trie s k v) -> Trie s k v -> Trie s k v
An upwards accumulation on the trie.
downwards :: Ord k => (Trie s k v -> Trie s k v) -> Trie s k v -> Trie s k v
A downwards accumulation on the trie.
Derived operations
takeWhile :: Ord k => (Trie s k v -> Bool) -> Trie s k v -> Trie s k v
Return the prefix of the trie satisfying f.
takeWhile' :: Ord k => (v -> Bool) -> Trie s k v -> Trie s k v
Return the prefix of the trie satisfying f on all values present.
fringe :: Ord k => Trie s k v -> Trie s k v
Return the fringe of the trie (the trie composed of only the leaf nodes).
Debugging
toTree :: k -> Trie s k v -> Tree (k, Maybe v)
Produced by Haddock version 0.7