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

Stability | beta |

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://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 Trie a
- type KeyString = ByteString
- type KeyElem = ByteStringElem
- empty :: Trie a
- null :: Trie a -> Bool
- singleton :: KeyString -> a -> Trie a
- size :: Trie a -> Int
- fromList :: [(KeyString, a)] -> Trie a
- toListBy :: (KeyString -> a -> b) -> Trie a -> [b]
- toList :: Trie a -> [(KeyString, a)]
- keys :: Trie a -> [KeyString]
- lookupBy :: (Maybe a -> Trie a -> b) -> KeyString -> Trie a -> b
- lookup :: KeyString -> Trie a -> Maybe a
- member :: KeyString -> Trie a -> Bool
- submap :: KeyString -> Trie a -> Trie a
- alterBy :: (KeyString -> a -> Maybe a -> Maybe a) -> KeyString -> a -> Trie a -> Trie a
- insert :: KeyString -> a -> Trie a -> Trie a
- adjust :: (a -> a) -> KeyString -> Trie a -> Trie a
- delete :: KeyString -> 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 :: (KeyString -> a -> Maybe b) -> Trie a -> Trie b
- filterMap :: (a -> Maybe b) -> Trie a -> Trie b

# Data types

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.

type KeyString = ByteStringSource

# Basic functions

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

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

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

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