Portability | portable (with CPP) |
---|---|
Stability | provisional |
Maintainer | wren@community.haskell.org |
Data.Trie.Internal
Contents
Description
- data Trie a
- showTrie :: Show a => Trie a -> String
- breakMaximalPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
- empty :: Trie a
- null :: Trie a -> Bool
- singleton :: ByteString -> a -> Trie a
- size :: Trie a -> Int
- foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b
- toListBy :: (ByteString -> a -> b) -> Trie a -> [b]
- lookupBy_ :: (Maybe a -> Trie a -> b) -> b -> (Trie a -> b) -> ByteString -> Trie a -> b
- submap :: ByteString -> Trie a -> Trie a
- alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a
- alterBy_ :: (ByteString -> a -> Maybe a -> Trie a -> (Maybe a, Trie a)) -> ByteString -> a -> Trie a -> Trie a
- adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
- mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
- mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b
- filterMap :: (a -> Maybe b) -> Trie a -> Trie b
- contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie b
- contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie b
- contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie b
- contextualMapBy :: (ByteString -> a -> Trie a -> Maybe b) -> Trie a -> Trie b
- minAssoc :: Trie a -> Maybe (ByteString, a)
- maxAssoc :: Trie a -> Maybe (ByteString, a)
- updateMinViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)
- updateMaxViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)
Data types
A map from ByteString
s 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.
Functions for ByteString
s
breakMaximalPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)Source
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
singleton :: ByteString -> a -> Trie aSource
O(1), Construct a singleton trie.
Conversion and folding functions
foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> bSource
Convert a trie into a list (in key-sorted order) using a function, folding the list as we go.
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]Source
Convert a trie into a list using a function. Resulting values are in key-sorted order.
Query functions
lookupBy_ :: (Maybe a -> Trie a -> b) -> b -> (Trie a -> b) -> ByteString -> Trie a -> bSource
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.
submap :: ByteString -> Trie a -> Trie aSource
Return the subtrie containing all keys beginning with a prefix.
Single-value modification
alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie aSource
Generic function to alter a trie by one element with a function to resolve conflicts (or non-conflicts).
alterBy_ :: (ByteString -> a -> Maybe a -> Trie a -> (Maybe a, Trie a)) -> ByteString -> a -> Trie a -> Trie aSource
A variant of alterBy
which also allows modifying the sub-trie.
adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie aSource
Alter the value associated with a given key. If the key is not
present, then the trie is returned unaltered. See alterBy
if
you are interested in inserting new keys or deleting old keys.
Because this function does not need to worry about changing the
trie structure, it is somewhat faster than alterBy
.
Combining tries
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie aSource
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
filterMap :: (a -> Maybe b) -> Trie a -> Trie bSource
Apply a function to all values, potentially removing them.
contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie bSource
A variant of fmap
which provides access to the subtrie rooted
at each value.
contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie bSource
A variant of contextualMap
which applies the function strictly.
contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie bSource
A contextual variant of filterMap
.
contextualMapBy :: (ByteString -> a -> Trie a -> Maybe b) -> Trie a -> Trie bSource
A contextual variant of mapBy
. Again note that this is
expensive since we must reconstruct the keys.
Priority-queue functions
minAssoc :: Trie a -> Maybe (ByteString, a)Source
maxAssoc :: Trie a -> Maybe (ByteString, a)Source
updateMinViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)Source
updateMaxViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)Source