bytestring-trie-0.2.2: An efficient finite map from (byte)strings to values.Source codeContentsIndex
Data.Trie.Internal
Portabilityportable (with CPP)
Stabilityprovisional
Maintainerwren@community.haskell.org
Contents
Data types
Functions for ByteStrings
Basic functions
Conversion and folding functions
Query functions
Single-value modification
Combining tries
Mapping functions
Priority-queue functions
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 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
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
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
data Trie a Source

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.

show/hide Instances
showTrie :: Show a => Trie a -> StringSource
Visualization fuction for debugging.
Functions for ByteStrings
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
empty :: Trie aSource
O(1), Construct the empty trie.
null :: Trie a -> BoolSource
O(1), Is the trie empty?
singleton :: ByteString -> a -> Trie aSource
O(1), Construct a singleton trie.
size :: Trie a -> IntSource
O(n), Get count of elements in 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).
adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie aSource
...
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
mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie bSource
Generic version of fmap. This function is notably more expensive than fmap or filterMap because we have to reconstruct the keys.
filterMap :: (a -> Maybe b) -> Trie a -> Trie bSource
Apply a function to all values, potentially removing them.
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
Produced by Haddock version 2.6.0