bytestring-trie-0.2.2: An efficient finite map from (byte)strings to values. Source code Contents Index

Data.Trie.Convenience Portability portable Stability provisional Maintainer wren@community.haskell.org

Contents Conversion functions lookupBy variants alterBy variants mergeBy variants

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.

Synopsis

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 a Source

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

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 Source

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 Source

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

lookupBy variants

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

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

alterBy variants

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

Insert a new key, retaining old value on conflict.

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

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

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

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

Apply a function to change the value at a key.

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

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

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

mergeBy variants

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

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

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

Combine two tries, using a function to resolve conflicts.

Produced by Haddock version 2.6.1