Apply a two-argument function through a shallow DeepMap, akin to liftA2.

Apply a two-argument Map function through a deep DeepMap, akin to liftA2.

O(1). The empty, arbitrary positive-depth DeepMap.

O(1). A depth-1 DeepMap with a single key/value pair.

A singleton DeepMap. Use with (@|) to create deep nestings:

>>> "Outer" @> 0 @| [5]
Wrap {fromList [("Outer",Wrap {fromList [(0,Core [5])]})]}

Infix synonym for singleton. Use with (@>) to create deep nestings:

>>> "Outer" @> 0 @| [5]
Wrap {fromList [("Outer",Wrap {fromList [(0,Core [5])]})]}

O(n log n). Build a deeper DeepMap from a list of key/DeepMap pairs. If the list contains more than one value for the same key, the values are combined using (<>).

O(n log n). Build a depth-1 DeepMap from a list of key/value pairs. If the list contains more than one value for the same key, the values are combined using (<>).

O(n log n). Build a depth-2 DeepMap from a list of keys and values. If the list contains more than one value for the same keys, the values are combined using (<>).

O(n log n). Build a depth-3 DeepMap from a list of keys and values. If the list contains more than one value for the same keys, the values are combined using (<>).

O(n log n). Build a depth-4 DeepMap from a list of keys and values. If the list contains more than one value for the same keys, the values are combined using (<>).

O(n log n). Build a depth-5 DeepMap from a list of keys and values. If the list contains more than one value for the same keys, the values are combined using (<>).

O(n log n). Build a deeper DeepMap from a list of key/DeepMap pairs using the provided combining function.

O(n log n). Build a depth-1 DeepMap from a list of key/value pairs using the provided combining function.

O(n log n). Build a deeper DeepMap from a list of key/DeepMap pairs with a combining function.

O(n log n). Build a depth-1 DeepMap from a list of key/value pairs with a combining function.

O(n log n). Build a depth-2 DeepMap from a list of keys and values with a combining function.

O(n log n). Build a depth-3 DeepMap from a list of keys and values with a combining function.

O(n log n). Build a depth-3 DeepMap from a list of keys and values with a combining function.

O(n log n). Build a depth-3 DeepMap from a list of keys and values with a combining function.

Half of the isomorphism of a depth-1 DeepMap to a Map. See also fromMap.

Half of the isomorphism of a depth-1 DeepMap to a Map. See also toMap.

O(log n). Insert a key/DeepMap pair into the DeepMap. If the key is already present in the map, the associated value is combined with the new value as old <> new. The overwriting behaviour from containers can be recovered by wrapping values in Last or by using overwrite.

O(log n). Insert a new key and value into a depth-1 DeepMap. If the key is already present in the map, the associated value is combined with the new value as old <> new. The overwriting behaviour from containers can be recovered by wrapping values in Last or by using overwrite1.

O(log n). Insert a new key-chain/value pair into a depth-2 DeepMap. If the key is already present in the map, the associated value is combined with the new value as old <> new. The overwriting behaviour from containers can be recovered by wrapping values in Last or by using overwrite2.

O(log n). Insert a new key-chain/value pair into a depth-3 DeepMap. If the key is already present in the map, the associated value is combined with the new value as old <> new. so the overwriting behaviour from containers can be recovered by wrapping values in Last or by using overwrite3.

O(log n). Insert a new key-chain/value pair into a depth-4 DeepMap. If the key is already present in the map, the associated value is combined with the new value as old <> new. so the overwriting behaviour from containers can be recovered by wrapping values in Last or by using overwrite4.

O(log n). Insert a new key-chain/value pair into a depth-5 DeepMap. If the key is already present in the map, the associated value is combined with the new value as old <> new. so the overwriting behaviour from containers can be recovered by wrapping values in Last or by using overwrite5.

O(log n). Insert with a function, combining new value and old value using the supplied function.

insertWith (~~) k new m will insert new at k if there is no value present, or overwrite with old ~~ new if there was already a value old at k.

O(log n). Insert with a function, combining new value and old value using the supplied function.

insertWith1 (~~) k new m will insert new at k if there is no value present, or overwrite with old ~~ new if there was already a value old at k.

O(log n). Insert with a function, combining new value and old value using the supplied function.

O(log n). Insert with a function, combining new value and old value using the supplied function.

O(log n). Insert with a function, combining new value and old value using the supplied function.

O(log n). Insert with a function, combining new value and old value using the supplied function.

O(log n). Insert with a function, combining new value and old value using the supplied function.

insertWithKey f k new m will insert new at k if there is no value present, or f k old new if there was already a value old at k. The key passed to f is the one passed to insertWithKey, not the one present in the map.

O(log n). Insert with a function, combining new value and old value using the supplied function with access to the given keys.

O(log n). Insert with a function, combining new value and old value using the supplied function with access to the given keys.

O(log n). Insert with a function, combining new value and old value using the supplied function with access to the given keys.

O(log n). Insert with a function, combining new value and old value using the supplied function with access to the given keys.

O(log n). Insert with a function, combining new value and old value using the supplied function with access to the given keys.

O(log n). Combines insertion and retrieval.

'insertLookupWithKey' f k new == 'lookup' k &&& 'insertWithKey' f k new

O(log n). Combines insertion and retrieval.

O(log n). Combines insertion and retrieval.

O(log n). Combines insertion and retrieval.

O(log n). Combines insertion and retrieval.

O(log n). Combines insertion and retrieval.

O(log n). Insert a new key/DeepMap pair into the DeepMap. If the key is already present in the map, the associated value is replaced by the new value.

O(log n). Insert a new key/value pair into a depth-1 DeepMap. If the key is already present in the map, the associated value is replaced by the new value.

O(log n). Insert a new key-chain/value pair into a depth-2 DeepMap. If the key is already present in the map, the associated value is replaced by the new value.

O(log n). Insert a new key-chain/value pair into a depth-3 DeepMap. If the key is already present in the map, the associated value is replaced by the new value.

O(log n). Insert a new key-chain/value pair into a depth-4 DeepMap. If the key is already present in the map, the associated value is replaced by the new value.

O(log n). Insert a new key-chain/value pair into a depth-5 DeepMap. If the key is already present in the map, the associated value is replaced by the new value.

O(log n). Combines replacement and retrieval.

O(log n). Combines replacement and retrieval at depth 1.

O(log n). Combines replacement and retrieval at depth 2.

O(log n). Combines replacement and retrieval at depth 3.

O(log n). Combines replacement and retrieval at depth 4.

O(log n). Combines replacement and retrieval at depth 5.

O(log n). Delete a key and its value from the map, or do nothing if the key is missing.

O(log n). Delete a key and its value from the map, or do nothing if the key is missing.

O(log n). Delete a key and its value from the map, or do nothing if the key is missing.

O(log n). Delete a key and its value from the map, or do nothing if the key is missing.

O(log n). Delete a key and its value from the map, or do nothing if the key is missing.

O(log n). Delete a key and its value from the map, or do nothing if the key is missing.

O(log n). Change a value at a specific key with the result of the provided function, or do nothing if the key is missing.

O(log n). Change a value at a specific key with the result of the provided function, or do nothing if the key is missing.

O(log n). Change a value at specific keys with the result of the provided function, or do nothing if the key is missing.

O(log n). Change a value at specific keys with the result of the provided function, or do nothing if the key is missing.

O(log n). Change a value at specific keys with the result of the provided function, or do nothing if the key is missing.

O(log n). Change a value at specific keys with the result of the provided function, or do nothing if the key is missing.

O(log n). Change a value at a specific key with access to the key itself, or do nothing if the key is missing.

O(log n). Change a value at a specific key with access to the key itself, or do nothing if the key is missing.

O(log n). Change a value at a specific key with access to the key itself, or do nothing if the key is missing.

O(log n). Change a value at a specific key with access to the key itself, or do nothing if the key is missing.

O(log n). Change a value at a specific key with access to the key itself, or do nothing if the key is missing.

O(log n). Change a value at a specific key with access to the key itself, or do nothing if the key is missing.

O(log n). Change a DeepMap at a specific key. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a DeepMap at a specific key. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a DeepMap at a specific key. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a DeepMap at a specific key. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a DeepMap at a specific key. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a DeepMap at a specific key. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a DeepMap at a specific key, with access to the key itself. If the function evaluates to Nothing, the key and submap are removed. If the key is missing, do nothing.

O(log n). Change a value at a specific key with access to the key itself. If the function evaluates to Nothing, the key and value are removed. If the key is missing, do nothing.

O(log n). Change a value at specific keys with access to the keys themselves. If the function evaluates to Nothing, the keys and value are removed. If the keys are missing, do nothing.

O(log n). Change a value at specific keys with access to the keys themselves. If the function evaluates to Nothing, the keys and value are removed. If the keys are missing, do nothing.

O(log n). Change a value at specific keys with access to the keys themselves. If the function evaluates to Nothing, the keys and value are removed. If the keys are missing, do nothing.

O(log n). Change a value at specific keys with access to the keys themselves. If the function evaluates to Nothing, the keys and value are removed. If the keys are missing, do nothing.

O(log n). Combines change and retrieval.

'updateLookupWithKey' f k == 'lookup' k &&& 'updateWithKey' f k

O(log n). Combines change and retrieval.

O(log n). Combines change and retrieval.

O(log n). Combines change and retrieval.

O(log n). Combines change and retrieval.

O(log n). Combines change and retrieval.

O(log n). Can be used to insert, overwrite, delete, or update a value.

O(log n). Can be used to insert, overwrite, delete, or update a value.

O(log n). Can be used to insert, overwrite, delete, or update a value.

O(log n). Can be used to insert, overwrite, delete, or update a value.

O(log n). Can be used to insert, overwrite, delete, or update a value.

O(log n). Can be used to insert, overwrite, delete, or update a value.

O(log n). Lookup the value at a key.

O(log n). A flipped, infix variant of lookup.

O(log n). A flipped, infix variant of lookup1.

O(log n). Facilitates chaining of lookups. For m :: DeepMap '[k0, k1, k2] v,

>>> m @? k0 @?? k1 @??| k2 == (m @? k0) >>= (@? k1) >>= (@?| k2)

O(log n). Facilitates chaining of lookups. For m :: DeepMap '[k0, k1, k2] v,

>>> m @? k0 @?? k1 @??| k2 == (m @? k0) >>= (@? k1) >>= (@?| k2)

O(log n). A version of (@?) that returns mempty when the element cannot be found.

O(log n). A version of (@?|) that returns mempty when the element cannot be found.

O(log n). Lookup the DeepMap at a key, with a default if the key is missing.

O(log n). Lookup the value at a key, with a default if the key is missing.

O(log n). Lookup the value at a key, with a default if the key is missing.

O(log n). Lookup the value at a key, with a default if the key is missing.

O(log n). Lookup the value at a key, with a default if the key is missing.

O(log n). Lookup the value at a key, with a default if the key is missing.

O(log n). Is the key a member of the map? See also notMember.

O(log n). Is the key missing from the map? See also member.

Find the next smallest key to the given one, and return its key/value pair.

Find the next largest key to the given one, and return its key/value pair.

Find the largest key up to the given one, and return its key/value pair.

Find the smallest key down to the given one, and return its key/value pair.

O(1). Is the DeepMap empty?

O(1). The number of outermost keys in the DeepMap.

O(m log(n / m + 1)), m <= n. Join two DeepMaps together using (<>) to combine the values of duplicate keys.

To retain Map's left-biased functionality, use unionWith const.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function.

O(m log(n / m + 1)), m <= n. Join two maps with a combining function with access to the keys.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function with access to the keys.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function with access to the keys.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function with access to the keys.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function with access to the keys.

O(m log(n / m + 1)), m <= n. Join two DeepMaps with a combining function with access to the keys.

A synonym for fold. To retain Map's functionality, use unionsWith const.

The union of a list of DeepMaps, combining with a specified operation.

The union of a list of DeepMaps, combining with a specified operation.

O(m log(n / m + 1)), m <= n. The set-difference of the keys in a DeepMap, keeping the values of the left-hand map.

Infix synonym for difference.

O(n + m). Difference with a combining function. Deletes keys if the value is Nothing.

O(n + m). Difference with a combining function. Deletes keys if the value is Nothing.

O(n + m). Difference with a combining function. Deletes keys if the value is Nothing.

O(n + m). Difference with a combining function. Deletes keys if the value is Nothing.

O(m log(n / m + 1)), m <= n. The set-intersection of the keys in a map, keeping the values of the left-hand map.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(m log(n / m + 1)), m <= n. Intersection with a combining function.

O(n). Strictly more general than fmap in that it may change the types of the inner keys.

O(n). Like mapShallow but the function has access to the outer keys.

O(n). Like fmap but the function has access to the outer keys.

O(n). Like fmap but the function has access to the outer keys.

O(n). Like fmap but the function has access to the outer keys.

O(n). Like fmap but the function has access to the outer keys.

O(n). Like fmap but the function has access to the outer keys.

O(n). Strictly more general than traverse in that it may change the types of the inner keys.

O(n). Like traverseShallow but the function has access to the keys.

O(n). Like traverse but the function has access to the keys.

O(n). Like traverse but the function has access to the keys.

O(n). Like traverse but the function has access to the keys.

O(n). Like traverse but the function has access to the keys.

O(n). Like traverse but the function has access to the keys.

O(n). Traverse keys/submaps and collect the Just results.

O(n). Traverse keys/values and collect the Just results.

O(n). Traverse keys/values and collect the Just results.

O(n). Traverse keys/values and collect the Just results.

O(n). Traverse keys/values and collect the Just results.

O(n). Traverse keys/values and collect the Just results.

O(n). Thread an accumulating argument through the DeepMap in ascending order of keys.

O(n). Thread an accumulating argument through the DeepMap in ascending order of keys.

O(n). Thread an accumulating argument through the DeepMap in descending order of keys.

O(n). Thread an accumulating argument through the DeepMap in descending order of keys.

O(n). Like mapAccum but the function has access to the keys.

O(n). Like mapAccum but the function has access to the keys.

O(n). Like mapAccum but the function has access to the keys.

O(n). Like mapAccum but the function has access to the keys.

O(n). Like mapAccum but the function has access to the keys.

O(n). Like mapAccum but the function has access to the keys.

O(n). Like mapAccumR but the function has access to the keys.

O(n). Like mapAccumR but the function has access to the keys.

O(n). Like mapAccumR but the function has access to the keys.

O(n). Like mapAccumR but the function has access to the keys.

O(n). Like mapAccumR but the function has access to the keys.

O(n). Like mapAccumR but the function has access to the keys.

O(n log n). Map a function over the outer keys of a DeepMap. If the function maps two or more j-keys to the same k-key, the values of the j-keys are combined with (<>).

To retain Map's greatest-biased functionality, use mapKeysWith const.

O(n log n). Map a function over the keys of a DeepMap.

O(n log n). Map a function over the keys of a DeepMap.

O(n log n). Map a function over the keys of a DeepMap.

O(n log n). Map a function over the keys of a DeepMap.

O(n log n). Map a function over the keys of a DeepMap.

O(n log n). Map a function over the outer keys of a DeepMap with a combining function.

O(n log n). Map a function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a function over the keys of a DeepMap with a value-combining function.

O(n log n). Map an applicative function over the outer keys and collect the results.

O(n log n). Map an applicative function over the outer keys of the map and collect the results using the specified combining function.

O(n log n). Map a monadic function over the keys of a DeepMap and collect the results.

O(n log n). Map a monadic function over the keys of a DeepMap and collect the results.

O(n log n). Map a monadic function over the keys of a DeepMap and collect the results.

Sadly traverseKeys2 can't have this type signature because we'd end up with a twice-wrapped Applicative and no way out.

O(n log n). Map a monadic function over the keys of a DeepMap and collect the results.

O(n log n). Map a monadic function over the keys of a DeepMap and collect the results.

O(n log n). Map a monadic function over the keys of a DeepMap and collect the results.

O(n log n). Map a monadic function over the outer keys of a DeepMap with a submap-combining function.

O(n log n). Map a monadic function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a monadic function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a monadic function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a monadic function over the keys of a DeepMap with a value-combining function.

O(n log n). Map a monadic function over the keys of a DeepMap with a value-combining function.

Right-associative fold of a structure, lazy in the accumulator.

In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Note that since the head of the resulting expression is produced by an application of the operator to the first element of the list, given an operator lazy in its right argument, foldr can produce a terminating expression from an unbounded list.

For a general Foldable structure this should be semantically identical to,

foldr f z = foldr f z . toList

Examples

>>> foldr (||) False [False, True, False]
True

>>> foldr (||) False []
False

>>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
"foodcba"

>>> foldr (||) False (True : repeat False)
True

>>> foldr (||) False (repeat False ++ [True])
* Hangs forever *

>>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
[1,4,7,10,13]

Left-associative fold of a structure, lazy in the accumulator. This is rarely what you want, but can work well for structures with efficient right-to-left sequencing and an operator that is lazy in its left argument.

In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Note that to produce the outermost application of the operator the entire input list must be traversed. Like all left-associative folds, foldl will diverge if given an infinite list.

If you want an efficient strict left-fold, you probably want to use foldl' instead of foldl. The reason for this is that the latter does not force the inner results (e.g. z `f` x1 in the above example) before applying them to the operator (e.g. to (`f` x2)). This results in a thunk chain O(n) elements long, which then must be evaluated from the outside-in.

For a general Foldable structure this should be semantically identical to:

foldl f z = foldl f z . toList

Examples

>>> foldl (+) 42 [1,2,3,4]
52

>>> foldl (\acc c -> c : acc) "abcd" "efgh"
"hgfeabcd"

>>> foldl (\a _ -> a) 0 $ repeat 1
* Hangs forever *

O(n). Fold the keys and submaps in the DeepMap using the given right-associative binary operator.

O(n). Fold the keys and values using the given right-associative binary operator.

O(n). Fold the keys and values using the given right-associative binary operator.

O(n). Fold the keys and values using the given right-associative binary operator.

O(n). Fold the keys and values using the given right-associative binary operator.

O(n). Fold the keys and values using the given right-associative binary operator.

O(n). Fold the keys and submaps in the DeepMap using the given left-associative binary operator.

O(n). Fold the keys and values in the DeepMap using the given left-associative binary operator.

O(n). Fold the keys and values in the DeepMap using the given left-associative binary operator.

O(n). Fold the keys and values in the DeepMap using the given left-associative binary operator.

O(n). Fold the keys and values in the DeepMap using the given left-associative binary operator.

O(n). Strictly fold the keys and values in the DeepMap using the given left-associative binary operator.

O(n). Fold the keys and submaps using the given monoid.

O(n). Fold the keys and values in the map using the given monoid.

O(n). Fold the keys and values in the map using the given monoid.

O(n). Fold the keys and values in the map using the given monoid.

O(n). Fold the keys and values in the map using the given monoid.

O(n). Fold the keys and values in the map using the given monoid.

foldr' is a variant of foldr that performs strict reduction from right to left, i.e. starting with the right-most element. The input structure must be finite, otherwise foldr' runs out of space (diverges).

If you want a strict right fold in constant space, you need a structure that supports faster than O(n) access to the right-most element, such as Seq from the containers package.

This method does not run in constant space for structures such as lists that don't support efficient right-to-left iteration and so require O(n) space to perform right-to-left reduction. Use of this method with such a structure is a hint that the chosen structure may be a poor fit for the task at hand. If the order in which the elements are combined is not important, use foldl' instead.

Since: base-4.6.0.0

Left-associative fold of a structure but with strict application of the operator.

This ensures that each step of the fold is forced to Weak Head Normal Form before being applied, avoiding the collection of thunks that would otherwise occur. This is often what you want to strictly reduce a finite structure to a single strict result (e.g. sum).

For a general Foldable structure this should be semantically identical to,

foldl' f z = foldl' f z . toList

Since: base-4.6.0.0

O(n). Strictly fold the keys and submaps in the DeepMap using the given right-associative binary operator.

O(n). Strictly fold the keys and values using the given right-associative binary operator.

O(n). Strictly fold the keys and values using the given right-associative binary operator.

O(n). Strictly fold the keys and values using the given right-associative binary operator.

O(n). Strictly fold the keys and values using the given right-associative binary operator.

O(n). Strictly fold the keys and values using the given right-associative binary operator.

O(n). Strictly fold the keys and submaps in the DeepMap using the given left-associative binary operator.

O(n). Strictly fold the keys and values in the DeepMap using the given left-associative binary operator.

O(n). Strictly fold the keys and values in the DeepMap using the given left-associative binary operator.