| Portability | portable |
|---|---|
| Stability | provisional |
| Maintainer | wren@community.haskell.org |
Data.Trie.Convenience
Description
Additional convenience functions. In order to keep Data.Trie concise, non-essential and uncommonly used functions have been moved here. Most of these functions simplify the generic functions from Data.Trie, following after the interface for Data.Map and Data.IntMap.
- fromListL :: [(ByteString, a)] -> Trie a
- fromListR :: [(ByteString, a)] -> Trie a
- fromListS :: [(ByteString, a)] -> Trie a
- fromListWith :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
- lookupWithDefault :: a -> ByteString -> Trie a -> a
- insertIfAbsent :: ByteString -> a -> Trie a -> Trie a
- insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
- insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
- adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a
- update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a
- updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a
- disunion :: Trie a -> Trie a -> Trie a
- unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
Conversion functions
Just like fromList all of these functions convert an association
list into a trie, with earlier values shadowing later ones when
keys conflict. Depending on the order of keys in the list, there
can be as much as 5x speed difference between the left and right
variants. Yet, performance is about the same when matching
best-case to best-case and worst-case to worst-case (which is
which is swapped when reversing the list or changing which
function is used).
fromListL :: [(ByteString, a)] -> Trie aSource
fromListR :: [(ByteString, a)] -> Trie aSource
fromListS :: [(ByteString, a)] -> Trie aSource
This version sorts the list before folding over it. This adds O(n log n) overhead and requires the whole list be in memory at once, but it ensures that the list is in best-case order. The benefits generally outweigh the costs.
fromListWith :: (a -> a -> a) -> [(ByteString, a)] -> Trie aSource
A variant of fromListR that takes a function for combining values on conflict.
lookupBy variants
lookupWithDefault :: a -> ByteString -> Trie a -> aSource
Lookup a key, returning a default value if it's not found.
alterBy variants
insertIfAbsent :: ByteString -> a -> Trie a -> Trie aSource
Insert a new key, retaining old value on conflict.
insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie aSource
Insert a new key, with a function to resolve conflicts.
insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie aSource
adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie aSource
Apply a function to change the value at a key.
update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie aSource
Apply a function to the value at a key, possibly removing it.
updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie aSource