|
Data.Trie | Portability | portable | Stability | experimental | Maintainer | wren@community.haskell.org |
|
|
|
|
|
Description |
An efficient implementation of finite maps from strings to values.
The implementation is based on big-endian patricia trees, like
Data.IntMap. We first trie on the elements of Data.ByteString
and then trie on the big-endian bit representation of those
elements. For further details on the latter, see
- Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps",
Workshop on ML, September 1998, pages 77-86,
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452
- D.R. Morrison, "PATRICIA -- Practical Algorithm To Retrieve
Information Coded In Alphanumeric", Journal of the ACM, 15(4),
October 1968, pages 514-534.
This module aims to provide an austere interface, while being
detailed enough for most users. For an extended interface with
many additional functions, see Data.Trie.Convenience.
|
|
Synopsis |
|
|
|
|
Data type
|
|
|
A map from ByteStrings to a. For all the generic functions,
note that tries are strict in the Maybe but not in a.
The Monad instance is strange. If a key k1 is a prefix of
other keys, then results from binding the value at k1 will
override values from longer keys when they collide. If this is
useful for anything, or if there's a more sensible instance, I'd
be curious to know.
| Instances | |
|
|
Basic functions
|
|
|
O(1), Construct the empty trie.
|
|
|
O(1), Is the trie empty?
|
|
|
O(1), Construct a singleton trie.
|
|
|
O(n), Get count of elements in trie.
|
|
Conversion functions
|
|
|
Convert association list into a trie. On key conflict, values
earlier in the list shadow later ones.
|
|
|
Convert a trie into a list using a function. Resulting values
are in key-sorted order.
|
|
|
Convert trie into association list. Keys will be in sorted order.
|
|
|
Return all keys in the trie, in sorted order.
|
|
|
Return all values in the trie, in sorted order according to the keys.
|
|
Query functions
|
|
|
Generic function to find a value (if it exists) and the subtrie
rooted at the prefix.
|
|
|
Return the value associated with a query string if it exists.
|
|
|
Does a string have a value in the trie?
|
|
|
Return the subtrie containing all keys beginning with a prefix.
|
|
Single-value modification
|
|
|
Generic function to alter a trie by one element with a function
to resolve conflicts (or non-conflicts).
|
|
|
Insert a new key. If the key is already present, overrides the
old value
|
|
|
Apply a function to the value at a key.
|
|
|
Remove the value stored at a key.
|
|
Combining tries
|
|
|
Combine two tries, using a function to resolve collisions.
This can only define the space of functions between union and
symmetric difference but, with those two, all set operations can
be defined (albeit inefficiently).
|
|
|
Combine two tries, resolving conflicts by choosing the value
from the left trie.
|
|
|
Combine two tries, resolving conflicts by choosing the value
from the right trie.
|
|
Mapping functions
|
|
|
Generic version of fmap. This function is notably more
expensive than fmap or filterMap because we have to reconstruct
the keys.
|
|
|
Apply a function to all values, potentially removing them.
|
|
Produced by Haddock version 2.6.1 |