Data.Trie

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.

Data type

data Trie a

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

Monad Trie

Functor Trie

Applicative Trie

Foldable Trie

Traversable Trie

Eq a => Eq (Trie a)

Show a => Show (Trie a)

Monoid a => Monoid (Trie a)

Binary a => Binary (Trie a)

Basic functions

empty :: Trie a

O(1), Construct the empty trie.

null :: Trie a -> Bool

O(1), Is the trie empty?

singleton :: ByteString -> a -> Trie a

O(1), Construct a singleton trie.

size :: Trie a -> Int

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

Conversion functions

fromList :: [(ByteString, a)] -> Trie a

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

toListBy :: (ByteString -> a -> b) -> Trie a -> [b]

Convert a trie into a list using a function. Resulting values are in key-sorted order.

toList :: Trie a -> [(ByteString, a)]

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

keys :: Trie a -> [ByteString]

Return all keys in the trie, in sorted order.

elems :: Trie a -> [a]

Return all values in the trie, in sorted order according to the keys.

Query functions

lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b

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

lookup :: ByteString -> Trie a -> Maybe a

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

member :: ByteString -> Trie a -> Bool

Does a string have a value in the trie?

submap :: ByteString -> Trie a -> Trie a

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 a

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

insert :: ByteString -> a -> Trie a -> Trie a

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

adjust :: (a -> a) -> ByteString -> Trie a -> Trie a

Apply a function to the value at a key.

delete :: ByteString -> Trie a -> Trie a

Remove the value stored at a key.

Combining tries

mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a

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 a

Combine two tries, resolving conflicts by choosing the value from the left trie.

unionR :: Trie a -> Trie a -> Trie a

Combine two tries, resolving conflicts by choosing the value from the right trie.

Mapping functions

mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b

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

Apply a function to all values, potentially removing them.