Data.Map (original) (raw)
Description
Finite Maps (lazy interface)
This module re-exports the value lazy Data.Map.Lazy API.
The `[Map](Data-Map-Strict.html#t:Map "Data.Map.Strict")` k v type represents a finite map (sometimes called a dictionary) from keys of type k to values of type v. A [Map](Data-Map-Strict.html#t:Map "Data.Map.Strict") 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](Data-Map-Strict.html#t:Map "Data.Map.Strict"). 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](/package/base-4.18.1.0/docs/Data-Int.html#t:Int "Data.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.Lazyfrom theunordered-containers package instead.
For a walkthrough of the most commonly used functions see themaps 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](Data-Map-Strict.html#v:union "Data.Map.Strict") and [intersection](Data-Map-Strict.html#v:intersection "Data.Map.Strict"), prefer the values in the first argument to those in the second.
Warning
The size of a [Map](Data-Map-Strict.html#t:Map "Data.Map.Strict") must not exceed `[maxBound](/package/base-4.18.1.0/docs/Prelude.html#v:maxBound "Prelude")` :: `[Int](/package/base-4.18.1.0/docs/Data-Int.html#t:Int "Data.Int")`. Violation of this condition is not detected and if the size limit is exceeded, its behaviour is undefined.
Implementation
The implementation of [Map](Data-Map-Strict.html#t:Map "Data.Map.Strict") 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](Data-Map-Strict.html#v:union "Data.Map.Strict"), [intersection](Data-Map-Strict.html#v:intersection "Data.Map.Strict"), and [difference](Data-Map-Strict.html#v:difference "Data.Map.Strict") are as given by
- Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Parallel Ordered Sets Using Join",https://arxiv.org/abs/1602.02120v4.
Performance information
The time complexity is given for each operation inbig-O notation, with \(n\) referring to the number of entries in the map.
Operations like [lookup](Data-Map-Strict.html#v:lookup "Data.Map.Strict"), [insert](Data-Map-Lazy.html#v:insert "Data.Map.Lazy"), and [delete](Data-Map-Strict.html#v:delete "Data.Map.Strict") take \(O(\log n)\) time.
Binary set operations like [union](Data-Map-Strict.html#v:union "Data.Map.Strict") and [intersection](Data-Map-Strict.html#v:intersection "Data.Map.Strict") take\(O\bigl(m \log\bigl(\frac{n}{m}+1\bigr)\bigr)\) time, where \(m\) and \(n\) are the sizes of the smaller and larger input maps respectively.