Convert to cabal.project
[packages/containers.git] / containers / src / Data / Map / Strict.hs
1 {-# LANGUAGE CPP #-}
2 {-# LANGUAGE BangPatterns #-}
3 #if defined(__GLASGOW_HASKELL__)
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 'Prelude.Int' keys, you will get much better performance for
37 -- most 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 'Data.Functor.Functor', 'Data.Traversable.Traversable' and
74 -- 'Data.Data.Data' instances are the same as for the "Data.Map.Lazy" module, so
75 -- if they are used the resulting 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 -- * Construction
108 , empty
109 , singleton
110 , fromSet
111
112 -- ** From Unordered Lists
113 , fromList
114 , fromListWith
115 , fromListWithKey
116
117 -- ** From Ascending Lists
118 , fromAscList
119 , fromAscListWith
120 , fromAscListWithKey
121 , fromDistinctAscList
122
123 -- ** From Descending Lists
124 , fromDescList
125 , fromDescListWith
126 , fromDescListWithKey
127 , fromDistinctDescList
128
129 -- * Insertion
130 , insert
131 , insertWith
132 , insertWithKey
133 , insertLookupWithKey
134
135 -- * Deletion\/Update
136 , delete
137 , adjust
138 , adjustWithKey
139 , update
140 , updateWithKey
141 , updateLookupWithKey
142 , alter
143 , alterF
144
145 -- * Query
146 -- ** Lookup
147 , lookup
148 , (!?)
149 , (!)
150 , findWithDefault
151 , member
152 , notMember
153 , lookupLT
154 , lookupGT
155 , lookupLE
156 , lookupGE
157
158 -- ** Size
159 , null
160 , size
161
162 -- * Combine
163
164 -- ** Union
165 , union
166 , unionWith
167 , unionWithKey
168 , unions
169 , unionsWith
170
171 -- ** Difference
172 , difference
173 , (\\)
174 , differenceWith
175 , differenceWithKey
176
177 -- ** Intersection
178 , intersection
179 , intersectionWith
180 , intersectionWithKey
181
182 -- ** General combining functions
183 -- | See "Data.Map.Merge.Strict"
184
185 -- ** Deprecated general combining function
186
187 , mergeWithKey
188
189 -- * Traversal
190 -- ** Map
191 , map
192 , mapWithKey
193 , traverseWithKey
194 , traverseMaybeWithKey
195 , mapAccum
196 , mapAccumWithKey
197 , mapAccumRWithKey
198 , mapKeys
199 , mapKeysWith
200 , mapKeysMonotonic
201
202 -- * Folds
203 , foldr
204 , foldl
205 , foldrWithKey
206 , foldlWithKey
207 , foldMapWithKey
208
209 -- ** Strict folds
210 , foldr'
211 , foldl'
212 , foldrWithKey'
213 , foldlWithKey'
214
215 -- * Conversion
216 , elems
217 , keys
218 , assocs
219 , keysSet
220
221 -- ** Lists
222 , toList
223
224 -- ** Ordered lists
225 , toAscList
226 , toDescList
227
228 -- * Filter
229 , filter
230 , filterWithKey
231 , restrictKeys
232 , withoutKeys
233 , partition
234 , partitionWithKey
235
236 , takeWhileAntitone
237 , dropWhileAntitone
238 , spanAntitone
239
240 , mapMaybe
241 , mapMaybeWithKey
242 , mapEither
243 , mapEitherWithKey
244
245 , split
246 , splitLookup
247 , splitRoot
248
249 -- * Submap
250 , isSubmapOf, isSubmapOfBy
251 , isProperSubmapOf, isProperSubmapOfBy
252
253 -- * Indexed
254 , lookupIndex
255 , findIndex
256 , elemAt
257 , updateAt
258 , deleteAt
259 , take
260 , drop
261 , splitAt
262
263 -- * Min\/Max
264 , lookupMin
265 , lookupMax
266 , findMin
267 , findMax
268 , deleteMin
269 , deleteMax
270 , deleteFindMin
271 , deleteFindMax
272 , updateMin
273 , updateMax
274 , updateMinWithKey
275 , updateMaxWithKey
276 , minView
277 , maxView
278 , minViewWithKey
279 , maxViewWithKey
280
281 -- * Debugging
282 #ifdef __GLASGOW_HASKELL__
283 , showTree
284 , showTreeWith
285 #endif
286 , valid
287 ) where
288
289 import Data.Map.Strict.Internal
290 import Prelude ()