Portability | portable |
---|---|

Stability | experimental |

Maintainer | wren@community.haskell.org |

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. For functions that give more detailed (potentially abstraction-breaking) access to the data strucuture, or for experimental functions which aren't quite ready for the public API, see Data.Trie.Internal.

- data Trie a
- empty :: Trie a
- null :: Trie a -> Bool
- singleton :: ByteString -> a -> Trie a
- size :: Trie a -> Int
- fromList :: [(ByteString, a)] -> Trie a
- toListBy :: (ByteString -> a -> b) -> Trie a -> [b]
- toList :: Trie a -> [(ByteString, a)]
- keys :: Trie a -> [ByteString]
- elems :: Trie a -> [a]
- lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
- lookup :: ByteString -> Trie a -> Maybe a
- member :: ByteString -> Trie a -> Bool
- submap :: ByteString -> Trie a -> Trie a
- alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a
- insert :: ByteString -> a -> Trie a -> Trie a
- adjust :: (a -> a) -> ByteString -> Trie a -> Trie a
- delete :: ByteString -> Trie a -> Trie a
- mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
- unionL :: Trie a -> Trie a -> Trie a
- unionR :: Trie a -> Trie a -> Trie a
- mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b
- filterMap :: (a -> Maybe b) -> Trie a -> Trie b

# Data type

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.

# Basic functions

singleton :: ByteString -> a -> Trie aSource

*O(1)*, Construct a singleton trie.

# Conversion functions

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

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

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

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

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

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

keys :: Trie a -> [ByteString]Source

Return all keys in the trie, in sorted order.

# Query functions

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

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

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

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

member :: ByteString -> Trie a -> BoolSource

Does a string have a value in the trie?

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

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 aSource

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

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

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

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

Apply a function to the value at a key.

delete :: ByteString -> 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.