bytestring-trie-0.2.4.1: An efficient finite map from (byte)strings to values.

CopyrightCopyright (c) 2008--2015 wren gayle romano
LicenseBSD3
Maintainerwren@community.haskell.org
Stabilityprovisional
Portabilityportable (with CPP)
Safe HaskellNone
LanguageHaskell98

Data.Trie.Internal

Contents

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

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.

Instances

showTrie :: Show a => Trie a -> String Source

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 a Source

O(1), Construct the empty trie.

null :: Trie a -> Bool Source

O(1), Is the trie empty?

singleton :: ByteString -> a -> Trie a Source

O(1), Construct a singleton trie.

size :: Trie a -> Int Source

O(n), Get count of elements in trie.

Conversion and folding functions

foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b Source

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 -> b Source

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 a Source

Return the subtrie containing all keys beginning with a prefix.

match_ :: Trie a -> ByteString -> Maybe (Int, a) Source

Given a query, find the longest prefix with an associated value in the trie, returning the length of that prefix and the associated value.

This function may not have the most useful return type. For a version that returns the prefix itself as well as the remaining string, see match in Data.Trie.

matches_ :: Trie a -> ByteString -> [(Int, a)] Source

Given a query, find all prefixes with associated values in the trie, returning their lengths and values. This function is a good producer for list fusion.

This function may not have the most useful return type. For a version that returns the prefix itself as well as the remaining string, see matches in Data.Trie.

Single-value modification

alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a Source

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 a Source

A variant of alterBy which also allows modifying the sub-trie.

adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a Source

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 a Source

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 b Source

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 b Source

Apply a function to all values, potentially removing them.

contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie b Source

A variant of fmap which provides access to the subtrie rooted at each value.

contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie b Source

A variant of contextualMap which applies the function strictly.

contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie b Source

A contextual variant of filterMap.

contextualMapBy :: (ByteString -> a -> Trie a -> Maybe b) -> Trie a -> Trie b Source

A contextual variant of mapBy. Again note that this is expensive since we must reconstruct the keys.

Priority-queue functions