Strict +Data.IntMap +containers
An efficient implementation of maps from integer keys to values (dictionaries).
API of this module is strict in both the keys and the values. If you need value-lazy maps, use Lazy instead. The IntMap type itself is shared between the lazy and strict modules, meaning that the same IntMap value can be passed to functions in both modules (although that is rarely needed).
These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
> import Data.IntMap.Strict (IntMap)
> import qualified Data.IntMap.Strict 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).
Be aware that the Functor, Traversable and Data instances are the same as for the Lazy module, so if they are used on strict maps, the resulting maps will be lazy.