Data.Trie

An efficient implementation of 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.

Data types

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

Foldable Trie

Traversable Trie

Eq a => Eq (Trie a)

Monoid a => Monoid (Trie a)

Binary a => Binary (Trie a)

type KeyString = ByteString

type KeyElem = ByteStringElem

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

Visualization fuction for debugging.

Basic functions

empty :: Trie a

O(1), The empty trie.

null :: Trie a -> Bool

O(1), Is the trie empty?

singleton :: KeyString -> a -> Trie a

O(1), A singleton trie.

size :: Trie a -> Int

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

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

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

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

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

Query functions

lookupBy_ :: (Maybe a -> Trie a -> b) -> b -> (Trie a -> b) -> KeyString -> Trie a -> b

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.

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

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

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

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

member :: KeyString -> Trie a -> Bool

Does a string have a value in the trie?

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

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 a

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

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

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

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

Apply a function to the value at a key.

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