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
A map from
a. For all the generic functions,
note that tries are strict in the
Maybe but not in
Monad instance is strange. If a key
k1 is a prefix of
other keys, then results from binding the value at
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.
Convert association list into a trie. On key conflict, values earlier in the list shadow later ones.
Convert a trie into a list using a function. Resulting values are in sorted order according to the keys.
Convert trie into association list. Keys will be in sorted order.
Generic function to find a value (if it exists) and the subtrie rooted at the prefix.
Return the value associated with a query string if it exists.
Return the subtrie containing all keys beginning with a prefix.
Generic function to alter a trie by one element with a function to resolve conflicts (or non-conflicts).
Insert a new key. If the key is already present, overrides the old value
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).
Combine two tries, resolving conflicts by choosing the value from the left trie.
Combine two tries, resolving conflicts by choosing the value from the right trie.