Finite Maps (lazy interface)
This module re-exports the value lazy
Data.Map.Lazy API.
The
Map k v type represents a finite map (sometimes
called a dictionary) from keys of type
k to values of type
v. A
Map is strict in its keys but lazy in its values.
The functions in
Data.Map.Strict are careful to force values
before installing them in a
Map. This is usually more efficient
in cases where laziness is not essential. The functions in this module
do not do so.
When deciding if this is the correct data structure to use, consider:
- If you are using Int keys, you will get much better
performance for most operations using Data.IntMap.Lazy.
- If you don't care about ordering, consider using
Data.HashMap.Lazy from the unordered-containers
package instead.
For a walkthrough of the most commonly used functions see the
maps
introduction.
This module is intended to be imported qualified, to avoid name
clashes with Prelude functions, e.g.
import Data.Map (Map)
import qualified Data.Map as Map
Note that the implementation is generally
left-biased.
Functions that take two maps as arguments and combine them, such as
union and
intersection, prefer the values in the first
argument to those in the second.
Warning
The size of a
Map must not exceed
maxBound ::
Int. Violation of this condition is not detected and if
the size limit is exceeded, its behaviour is undefined.
Implementation
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,
https://doi.org/10.1017/S0956796800000885,
https://groups.csail.mit.edu/mac/users/adams/BB/index.html.
- J. Nievergelt and E.M. Reingold, "Binary search trees of
bounded balance", SIAM journal of computing 2(1), March 1973.
https://doi.org/10.1137/0202005.
- Yoichi Hirai and Kazuhiko Yamamoto, "Balancing weight-balanced
trees", Journal of Functional Programming 21(3):287-307, 2011,
https://doi.org/10.1017/S0956796811000104
Bounds for
union,
intersection, and
difference
are as given by
Performance information
The time complexity is given for each operation in
big-O
notation, with <math> referring to the number of entries in
the map.
Operations like
lookup,
insert, and
delete take
<math> time.
Binary set operations like
union and
intersection take
<math> time, where <math> and <math> are the sizes
of the smaller and larger input maps respectively.