Portability | portable |
---|---|
Stability | provisional |
Maintainer | libraries@haskell.org |
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.