Data.Trie.Convenience

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.

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 a

fromListR :: [(ByteString, a)] -> Trie a

This version is just an alias for fromList. It is a good producer for list fusion. Worst-case behavior is somewhat worse than worst-case for fromListL.

fromListS :: [(ByteString, a)] -> Trie a

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 a

A variant of fromListR that takes a function for combining values on conflict.

lookupBy variants

lookupWithDefault :: a -> ByteString -> Trie a -> a

Lookup a key, returning a default value if it's not found.

alterBy variants

insertIfAbsent :: ByteString -> a -> Trie a -> Trie a

Insert a new key, retaining old value on conflict.

insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

Insert a new key, with a function to resolve conflicts.

insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a

Apply a function to change the value at a key.

update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a

Apply a function to the value at a key, possibly removing it.

updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a

mergeBy variants

disunion :: Trie a -> Trie a -> Trie a

Combine two tries. If they define the same key, it is removed.

unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a

Combine two tries, using a function to resolve conflicts.