Portability | portable (with CPP) |
---|---|

Stability | provisional |

Maintainer | wren@community.haskell.org |

- 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