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

Stability | provisional |

Maintainer | libraries@haskell.org |

Safe Haskell | Safe |

An efficient implementation of ordered maps from keys to values (dictionaries).

This module re-exports the value lazy Data.Map.Lazy API, plus
several deprecated value strict functions. Please note that these functions
have different strictness properties than those in Data.Map.Strict:
they only evaluate the values inserted into the map. For example, the
default value to `insertWith'`

is only evaluated if it's used, i.e. because
there's no value for the key already or because the higher-order argument
that combines the old and new value uses it.

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

import qualified Data.Map as Map

The implementation of `Map`

is based on *size balanced* binary trees (or
trees of *bounded balance*) as described by:

- Stephen Adams, "
*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. - J. Nievergelt and E.M. Reingold,
"
*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.

Note that the implementation is *left-biased* -- the elements of a
first argument are always preferred to the second, for example in
`union`

or `insert`

.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

- module Data.Map.Lazy
- insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
- fold :: (a -> b -> b) -> b -> Map k a -> b
- foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b

# Documentation

module Data.Map.Lazy

insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource

*Deprecated.* As of version 0.5, replaced by `insertWith`

.

*O(log n)*. Same as `insertWith`

, but the value being inserted to the map is
evaluated to WHNF beforehand. In contrast to `insertWith`

,
the value argument is not evaluted when not needed.

For example, to update a counter:

insertWith' (+) k 1 m

insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource

*Deprecated.* As of version 0.5, replaced by
`insertWithKey`

.

*O(log n)*. Same as `insertWithKey`

, but the value being inserted to the map is
evaluated to WHNF beforehand. In contrast to `insertWithKey`

,
the value argument is not evaluted when not needed.

insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)Source

*Deprecated.* As of version 0.5, replaced by
`insertLookupWithKey`

.

*O(log n)*. Same as `insertLookupWithKey`

, but the value being inserted to
the map is evaluated to WHNF beforehand. In contrast to
`insertLookupWithKey`

, the value argument is not evaluted
when not needed.

foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bSource

*Deprecated.* As of version 0.4, replaced by `foldrWithKey`

.

*O(n)*. Fold the keys and values in the map using the given right-associative
binary operator. This function is an equivalent of `foldrWithKey`

and is present
for compatibility only.