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

Stability | provisional |

Maintainer | [email protected] |

Safe Haskell | Trustworthy |

An efficient implementation of maps from integer 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 Data.IntMap (IntMap) import qualified Data.IntMap as IntMap

The implementation is based on *big-endian patricia trees*. This data
structure performs especially well on binary operations like `union`

and `intersection`

. However, my benchmarks show that it is also
(much) faster on insertions and deletions when compared to a generic
size-balanced map implementation (see Data.Map).

- Chris Okasaki and Andy Gill, "
*Fast Mergeable Integer Maps*", Workshop on ML, September 1998, pages 77-86, http://citeseer.ist.psu.edu/okasaki98fast.html - D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/", Journal of the ACM, 15(4), October 1968, pages 514-534.

Operation comments contain the operation time complexity in
the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation.
Many operations have a worst-case complexity of *O(min(n,W))*.
This means that the operation can become linear in the number of
elements with a maximum of *W* -- the number of bits in an `Int`

(32 or 64).

- module Data.IntMap.Lazy
- insertWith' :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
- insertWithKey' :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
- fold :: (a -> b -> b) -> b -> IntMap a -> b
- foldWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> b

# Documentation

module Data.IntMap.Lazy

insertWith' :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap aSource

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

.

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

, but the combining function is
applied strictly. This function is deprecated, use `insertWith`

in
Data.IntMap.Strict instead.

insertWithKey' :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap aSource

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

.

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

, but the combining function is
applied strictly. This function is deprecated, use `insertWithKey`

in Data.IntMap.Strict instead.

foldWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> bSource

*Deprecated.* As of version 0.5, 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.