Data.Trie.Internal

Internal definition of the Trie data type and generic functions for manipulating them. Almost everything here is re-exported from Data.Trie.

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.

Conversion functions

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

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

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. For the public-facing version, see lookupBy in Data.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).

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).

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.