Improve Data.Map (strict and lazy) module docs (#497)
[packages/containers.git] / Data / Map / Strict.hs
1 {-# LANGUAGE CPP #-}
2 {-# LANGUAGE BangPatterns #-}
3 #if __GLASGOW_HASKELL__ >= 703
4 {-# LANGUAGE Safe #-}
5 #endif
6
7 #include "containers.h"
8
9 -----------------------------------------------------------------------------
10 -- |
11 -- Module : Data.Map.Strict
12 -- Copyright : (c) Daan Leijen 2002
13 -- (c) Andriy Palamarchuk 2008
14 -- License : BSD-style
15 -- Maintainer : libraries@haskell.org
16 -- Portability : portable
17 --
18 --
19 -- = Finite Maps (strict interface)
20 --
21 -- The @'Map' k v@ type represents a finite map (sometimes called a dictionary)
22 -- from keys of type @k@ to values of type @v@.
23 --
24 -- Each function in this module is careful to force values before installing
25 -- them in a 'Map'. This is usually more efficient when laziness is not
26 -- necessary. When laziness /is/ required, use the functions in "Data.Map.Lazy".
27 --
28 -- In particular, the functions in this module obey the following law:
29 --
30 -- - If all values stored in all maps in the arguments are in WHNF, then all
31 -- values stored in all maps in the results will be in WHNF once those maps
32 -- are evaluated.
33 --
34 -- When deciding if this is the correct data structure to use, consider:
35 --
36 -- * If you are using 'Int' keys, you will get much better performance for most
37 -- operations using "Data.IntMap.Strict".
38 --
39 -- * If you don't care about ordering, consider use @Data.HashMap.Strict@ from the
40 -- <https://hackage.haskell.org/package/unordered-containers unordered-containers>
41 -- package instead.
42 --
43 -- For a walkthrough of the most commonly used functions see the
44 -- <https://haskell-containers.readthedocs.io/en/latest/map.html maps introduction>.
45 --
46 -- This module is intended to be imported qualified, to avoid name clashes with
47 -- Prelude functions:
48 --
49 -- > import qualified Data.Map.Strict as Map
50 --
51 -- Note that the implementation is generally /left-biased/. Functions that take
52 -- two maps as arguments and combine them, such as `union` and `intersection`,
53 -- prefer the values in the first argument to those in the second.
54 --
55 --
56 -- == Detailed performance information
57 --
58 -- The amortized running time is given for each operation, with /n/ referring to
59 -- the number of entries in the map.
60 --
61 -- Benchmarks comparing "Data.Map.Strict" with other dictionary implementations
62 -- can be found at https://github.com/haskell-perf/dictionaries.
63 --
64 --
65 -- == Warning
66 --
67 -- The size of a 'Map' must not exceed @maxBound::Int@. Violation of this
68 -- condition is not detected and if the size limit is exceeded, its behaviour is
69 -- undefined.
70 --
71 -- The 'Map' type is shared between the lazy and strict modules, meaning that
72 -- the same 'Map' value can be passed to functions in both modules. This means
73 -- that the 'Functor', 'Traversable' and 'Data' instances are the same as for
74 -- the "Data.Map.Lazy" module, so if they are used on strict maps, the resulting
75 -- maps may contain suspended values (thunks).
76 --
77 --
78 -- == Implementation
79 --
80 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
81 -- trees of /bounded balance/) as described by:
82 --
83 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
84 -- Journal of Functional Programming 3(4):553-562, October 1993,
85 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
86 -- * J. Nievergelt and E.M. Reingold,
87 -- \"/Binary search trees of bounded balance/\",
88 -- SIAM journal of computing 2(1), March 1973.
89 --
90 -- Bounds for 'union', 'intersection', and 'difference' are as given
91 -- by
92 --
93 -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
94 -- \"/Just Join for Parallel Ordered Sets/\",
95 -- <https://arxiv.org/abs/1602.02120v3>.
96 --
97 --
98 -----------------------------------------------------------------------------
99
100 -- See the notes at the beginning of Data.Map.Internal.
101
102 module Data.Map.Strict
103 (
104 -- * Map type
105 Map -- instance Eq,Show,Read
106
107 -- * Operators
108 , (!), (!?), (\\)
109
110 -- * Query
111 , null
112 , size
113 , member
114 , notMember
115 , lookup
116 , findWithDefault
117 , lookupLT
118 , lookupGT
119 , lookupLE
120 , lookupGE
121
122 -- * Construction
123 , empty
124 , singleton
125
126 -- ** Insertion
127 , insert
128 , insertWith
129 , insertWithKey
130 , insertLookupWithKey
131
132 -- ** Delete\/Update
133 , delete
134 , adjust
135 , adjustWithKey
136 , update
137 , updateWithKey
138 , updateLookupWithKey
139 , alter
140 , alterF
141
142 -- * Combine
143
144 -- ** Union
145 , union
146 , unionWith
147 , unionWithKey
148 , unions
149 , unionsWith
150
151 -- ** Difference
152 , difference
153 , differenceWith
154 , differenceWithKey
155
156 -- ** Intersection
157 , intersection
158 , intersectionWith
159 , intersectionWithKey
160
161 -- ** General combining functions
162 -- | See "Data.Map.Merge.Strict"
163
164 -- ** Deprecated general combining function
165
166 , mergeWithKey
167
168 -- * Traversal
169 -- ** Map
170 , map
171 , mapWithKey
172 , traverseWithKey
173 , traverseMaybeWithKey
174 , mapAccum
175 , mapAccumWithKey
176 , mapAccumRWithKey
177 , mapKeys
178 , mapKeysWith
179 , mapKeysMonotonic
180
181 -- * Folds
182 , foldr
183 , foldl
184 , foldrWithKey
185 , foldlWithKey
186 , foldMapWithKey
187
188 -- ** Strict folds
189 , foldr'
190 , foldl'
191 , foldrWithKey'
192 , foldlWithKey'
193
194 -- * Conversion
195 , elems
196 , keys
197 , assocs
198 , keysSet
199 , fromSet
200
201 -- ** Lists
202 , toList
203 , fromList
204 , fromListWith
205 , fromListWithKey
206
207 -- ** Ordered lists
208 , toAscList
209 , toDescList
210 , fromAscList
211 , fromAscListWith
212 , fromAscListWithKey
213 , fromDistinctAscList
214 , fromDescList
215 , fromDescListWith
216 , fromDescListWithKey
217 , fromDistinctDescList
218
219 -- * Filter
220 , filter
221 , filterWithKey
222 , restrictKeys
223 , withoutKeys
224 , partition
225 , partitionWithKey
226
227 , takeWhileAntitone
228 , dropWhileAntitone
229 , spanAntitone
230
231 , mapMaybe
232 , mapMaybeWithKey
233 , mapEither
234 , mapEitherWithKey
235
236 , split
237 , splitLookup
238 , splitRoot
239
240 -- * Submap
241 , isSubmapOf, isSubmapOfBy
242 , isProperSubmapOf, isProperSubmapOfBy
243
244 -- * Indexed
245 , lookupIndex
246 , findIndex
247 , elemAt
248 , updateAt
249 , deleteAt
250 , take
251 , drop
252 , splitAt
253
254 -- * Min\/Max
255 , lookupMin
256 , lookupMax
257 , findMin
258 , findMax
259 , deleteMin
260 , deleteMax
261 , deleteFindMin
262 , deleteFindMax
263 , updateMin
264 , updateMax
265 , updateMinWithKey
266 , updateMaxWithKey
267 , minView
268 , maxView
269 , minViewWithKey
270 , maxViewWithKey
271
272 -- * Debugging
273 , showTree
274 , showTreeWith
275 , valid
276 ) where
277
278 import Data.Map.Strict.Internal
279 import Prelude ()