Portability | portable |
---|---|

Stability | experimental |

Maintainer | wren@community.haskell.org |

- Conversion functions (
`fromList`

variants) - Query functions (
`lookupBy`

variants) - Inserting values (
`alterBy`

variants) - Updating and adjusting values (
`alterBy`

and`adjustBy`

variants) - Combining tries (
`mergeBy`

variants)

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
- fromListWith' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
- fromListWithL :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
- fromListWithL' :: (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
- insertWith' :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
- insertWithKey :: (ByteString -> 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
- unionWith' :: (a -> a -> a) -> Trie a -> Trie a -> Trie a

# 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 aSource

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

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

This variant 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. 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 aSource

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.

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

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`

.

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

A variant of `fromListWithL`

which applies the combining
function strictly.

# Query functions (`lookupBy`

variants)

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

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

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

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

A variant of `insertWith`

which applies the combining function
strictly.

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

A variant of `insertWith`

which also provides the key to the
combining function.

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

A variant of `insertWithKey`

which applies the combining
function strictly.

# Updating and adjusting values (`alterBy`

and `adjustBy`

variants)

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

A variant of `update`

which also provides the key to the function.

# Combining tries (`mergeBy`

variants)

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

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.