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 `Lazy`

API, plus
several value strict functions from `Strict`

.

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 combining function is
applied strictly. This is often the most desirable behavior.

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 combining function is
applied strictly.

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)*. A strict version of `insertLookupWithKey`

.

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.