Data.Trie.Convenience

Additional convenience versions of the generic functions.

lookupBy variants

lookupWithDefault :: a -> KeyString -> Trie a -> a

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

alterBy variants

insertIfAbsent :: KeyString -> a -> Trie a -> Trie a

Insert a new key, retaining old value on conflict.

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

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

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

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

Apply a function to change the value at a key.

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

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

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

Conversion functions

Just like fromList both 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 two. 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 :: [(KeyString, a)] -> Trie a

fromListR :: [(KeyString, 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 :: [(KeyString, 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.

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.