|
Data.Trie.Internal | Portability | portable (with CPP) | Stability | provisional | Maintainer | wren@community.haskell.org |
|
|
|
|
|
Description |
Internal definition of the Trie data type and generic functions
for manipulating them. Almost everything here is re-exported
from Data.Trie, which is the preferred API for users. This
module is for developers who need deeper (and potentially fragile)
access to the abstract type.
|
|
Synopsis |
|
|
|
|
Data types
|
|
|
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 | |
|
|
|
Visualization fuction for debugging.
|
|
Functions for ByteStrings
|
|
|
Returns the longest shared prefix and the two remaining suffixes
for a pair of strings.
s == (\(pre,s',z') -> pre `append` s') (breakMaximalPrefix s z)
z == (\(pre,s',z') -> pre `append` z') (breakMaximalPrefix s z)
|
|
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 and folding functions
|
|
|
Convert a trie into a list (in key-sorted order) using a
function, folding the list as we go.
|
|
|
Convert a trie into a list using a function. Resulting values
are in key-sorted order.
|
|
Query functions
|
|
|
Generic function to find a value (if it exists) and the subtrie
rooted at the prefix. The first function argument is called if and
only if a node is exactly reachable by the query; if no node is
exactly reachable the default value is used; if the middle of
an arc is reached, the second function argument is used.
This function is intended for internal use. For the public-facing
version, see lookupBy in Data.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).
|
|
|
...
|
|
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).
|
|
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.
|
|
Priority-queue functions
|
|
|
|
|
|
|
|
|
|
Produced by Haddock version 2.6.1 |