bytestring-trie-0.2.2: An efficient finite map from (byte)strings to values.Source codeContentsIndex
Data.Trie
Portabilityportable
Stabilityexperimental
Maintainerwren@community.haskell.org
Contents
Data type
Basic functions
Conversion functions
Query functions
Single-value modification
Combining tries
Mapping functions
Description

An efficient implementation of finite maps from strings to values. The implementation is based on big-endian patricia trees, like Data.IntMap. We first trie on the elements of Data.ByteString and then trie on the big-endian bit representation of those elements. For further details on the latter, see

  • Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452
  • D.R. Morrison, "PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric", Journal of the ACM, 15(4), October 1968, pages 514-534.

This module aims to provide an austere interface, while being detailed enough for most users. For an extended interface with many additional functions, see Data.Trie.Convenience.

Synopsis
data Trie a
empty :: Trie a
null :: Trie a -> Bool
singleton :: ByteString -> a -> Trie a
size :: Trie a -> Int
fromList :: [(ByteString, a)] -> Trie a
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]
toList :: Trie a -> [(ByteString, a)]
keys :: Trie a -> [ByteString]
elems :: Trie a -> [a]
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
lookup :: ByteString -> Trie a -> Maybe a
member :: ByteString -> Trie a -> Bool
submap :: ByteString -> Trie a -> Trie a
alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a
insert :: ByteString -> a -> Trie a -> Trie a
adjust :: (a -> a) -> ByteString -> Trie a -> Trie a
delete :: ByteString -> Trie a -> Trie a
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
unionL :: Trie a -> Trie a -> Trie a
unionR :: Trie a -> Trie a -> Trie a
mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b
filterMap :: (a -> Maybe b) -> Trie a -> Trie b
Data type
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
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 functions
fromList :: [(ByteString, a)] -> Trie aSource
Convert association list into a trie. On key conflict, values earlier in the list shadow later ones.
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]Source
Convert a trie into a list using a function. Resulting values are in key-sorted order.
toList :: Trie a -> [(ByteString, a)]Source
Convert trie into association list. Keys will be in sorted order.
keys :: Trie a -> [ByteString]Source
Return all keys in the trie, in sorted order.
elems :: Trie a -> [a]Source
Return all values in the trie, in sorted order according to the keys.
Query functions
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> bSource
Generic function to find a value (if it exists) and the subtrie rooted at the prefix.
lookup :: ByteString -> Trie a -> Maybe aSource
Return the value associated with a query string if it exists.
member :: ByteString -> Trie a -> BoolSource
Does a string have a value in the 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).
insert :: ByteString -> a -> Trie a -> Trie aSource
Insert a new key. If the key is already present, overrides the old value
adjust :: (a -> a) -> ByteString -> Trie a -> Trie aSource
Apply a function to the value at a key.
delete :: ByteString -> Trie a -> Trie aSource
Remove the value stored at a key.
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).
unionL :: Trie a -> Trie a -> Trie aSource
Combine two tries, resolving conflicts by choosing the value from the left trie.
unionR :: Trie a -> Trie a -> Trie aSource
Combine two tries, resolving conflicts by choosing the value from the right trie.
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.
Produced by Haddock version 2.6.1