Data.Trie

Note: performance is currently rather bad. See the benchmark directory. Please contribute :)

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

Fields

value :: !(Maybe v)

children :: !(Map k (Trie s k v))

Instances

Typeable3 Trie

Foldable (Trie s k)

(Eq k, Eq v) => Eq (Trie s k v)

(Show k, Show v) => Show (Trie [k] k v)

Ord k => Monoid (Trie s k v)

(Ord k, Sequence s k) => Map (Trie s k v) s v

(Ord k, Foldable s k) => Indexed (Trie s k v) s v

Sequence s k => Foldable (Trie s k v) (s, v)

(Ord k, Sequence s k) => Unfoldable (Trie s k v) (s, v)

(Ord k, Sequence s k) => Collection (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)