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 (fromList variants)

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

A left-fold version of fromList. If you run into issues with stack overflows when using fromList or fromListR, then you should use this function instead.

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

An explicitly right-fold variant of fromList. It is a good consumer for list fusion. Worst-case behavior is somewhat worse than worst-case for fromListL. The fromList function is currently just an alias for fromListR.

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

This variant sorts the list before folding over it. This adds \(\mathcal{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. The first argument to the combining function is the "new" value from the initial portion of the list; the second argument is the value that has been accumulated into the trie from the tail of the list (just like the first argument to foldr). Thus, fromList = fromListWith const.

fromListWith' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

A variant of fromListWith which applies the combining function strictly. This function is a good consumer for list fusion. If you need list fusion and are running into stack overflow problems with fromListWith, then this function may solve the problem.

Since: 0.2.3

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

A left-fold variant of fromListWith. Note that the arguments to the combining function are swapped: the first is the value in the trie which has been accumulated from the initial part of the list; the second argument is the "new" value from the remaining tail of the list (just like the first argument to foldl). Thus, fromListL = fromListWithL const.

Since: 0.2.3

fromListWithL' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

A variant of fromListWithL which applies the combining function strictly.

Since: 0.2.3

Query functions (lookupBy variants)

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

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

Inserting values (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.

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

A variant of insertWith which applies the combining function strictly.

Since: 0.2.3

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

A variant of insertWith which also provides the key to the combining function.

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

A variant of insertWithKey which applies the combining function strictly.

Since: 0.2.3

Updating and adjusting values (alterBy and adjustBy variants)

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

A variant of update which also provides the key to the function.

Combining tries (mergeBy and intersectBy variants)

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

Combine two tries, a la symmetric difference. If they define the same key, it is removed; otherwise it is retained with the value it has in whichever trie.

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

Take the union of two tries, using a function to resolve conflicts. The resulting trie is constructed strictly, but the results of the combining function are evaluated lazily.

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

A variant of unionWith which evaluates the combining function strictly.

Since: 0.2.3

intersectWith :: (a -> b -> c) -> Trie a -> Trie b -> Trie c

Take the intersection of two tries, with a function to resolve the values. The resulting trie is constructed strictly, bit the results of the combining function are evaluated lazily.

Since: 0.2.6

intersectWith' :: (a -> b -> c) -> Trie a -> Trie b -> Trie c

A variant of intersectWith which evaluates the combining function strictly.

Since: 0.2.6