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

Data.Trie

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://www.cse.ogi.edu/~andy/pub/finite.htm
• D.R. Morrison, "PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric", Journal of the ACM, 15(4), October 1968, pages 514-534.

Synopsis

# Data types

data Trie a Source

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.

Instances

 Monad Trie Functor Trie Foldable Trie Traversable Trie Eq a => Eq (Trie a) Monoid a => Monoid (Trie a) Binary a => Binary (Trie a)

type KeyElem = ByteStringElemSource

# Basic functions

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.