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





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,
  • D.R. Morrison, "PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric", Journal of the ACM, 15(4), October 1968, pages 514-534.


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.


type KeyElem = ByteStringElemSource

Basic functions

empty :: Trie aSource

O(1), The empty trie.

null :: Trie a -> BoolSource

O(1), Is the trie empty?

singleton :: KeyString -> a -> Trie aSource

O(1), A singleton trie.

size :: Trie a -> IntSource

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

Conversion functions

fromList :: [(KeyString, a)] -> Trie aSource

Convert association list into a trie. On key conflict, values earlier in the list shadow later ones.

toListBy :: (KeyString -> a -> b) -> Trie a -> [b]Source

Convert a trie into a list using a function. Resulting values are in sorted order according to the keys.

toList :: Trie a -> [(KeyString, a)]Source

Convert trie into association list. Keys will be in sorted order.

keys :: Trie a -> [KeyString]Source

Return all keys in the trie, in sorted order.

Query functions

lookupBy :: (Maybe a -> Trie a -> b) -> KeyString -> Trie a -> bSource

Generic function to find a value (if it exists) and the subtrie rooted at the prefix.

lookup :: KeyString -> Trie a -> Maybe aSource

Return the value associated with a query string if it exists.

member :: KeyString -> Trie a -> BoolSource

Does a string have a value in the trie?

submap :: KeyString -> Trie a -> Trie aSource

Return the subtrie containing all keys beginning with a prefix.

Single-value modification

alterBy :: (KeyString -> a -> Maybe a -> Maybe a) -> KeyString -> a -> Trie a -> Trie aSource

Generic function to alter a trie by one element with a function to resolve conflicts (or non-conflicts).

insert :: KeyString -> a -> Trie a -> Trie aSource

Insert a new key. If the key is already present, overrides the old value

adjust :: (a -> a) -> KeyString -> Trie a -> Trie aSource

Apply a function to the value at a key.

delete :: KeyString -> 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 :: (KeyString -> 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.