An efficient implementation of maps from integer keys to values
(dictionaries). 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 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