b80c90e15f7006efff6935100a481fcfe112a775
[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 -- An efficient implementation of ordered maps from keys to values
19 -- (dictionaries).
20 --
21 -- API of this module is strict in both the keys and the values.
22 -- If you need value-lazy maps, use "Data.Map.Lazy" instead.
23 -- The 'Map' type is shared between the lazy and strict modules,
24 -- meaning that the same 'Map' value can be passed to functions in
25 -- both modules (although that is rarely needed).
26 --
27 -- These modules are intended to be imported qualified, to avoid name
28 -- clashes with Prelude functions, e.g.
29 --
30 -- > import qualified Data.Map.Strict as Map
31 --
32 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
33 -- trees of /bounded balance/) as described by:
34 --
35 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
36 -- Journal of Functional Programming 3(4):553-562, October 1993,
37 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
38 -- * J. Nievergelt and E.M. Reingold,
39 -- \"/Binary search trees of bounded balance/\",
40 -- SIAM journal of computing 2(1), March 1973.
41 --
42 -- Bounds for 'union', 'intersection', and 'difference' are as given
43 -- by
44 --
45 -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
46 -- \"/Just Join for Parallel Ordered Sets/\",
47 -- <https://arxiv.org/abs/1602.02120v3>.
48 --
49 -- Note that the implementation is /left-biased/ -- the elements of a
50 -- first argument are always preferred to the second, for example in
51 -- 'union' or 'insert'.
52 --
53 -- /Warning/: The size of the map must not exceed @maxBound::Int@. Violation of
54 -- this condition is not detected and if the size limit is exceeded, its
55 -- behaviour is undefined.
56 --
57 -- Operation comments contain the operation time complexity in
58 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
59 --
60 -- Be aware that the 'Functor', 'Traversable' and 'Data' instances
61 -- are the same as for the "Data.Map.Lazy" module, so if they are used
62 -- on strict maps, the resulting maps will be lazy.
63 -----------------------------------------------------------------------------
64
65 -- See the notes at the beginning of Data.Map.Internal.
66
67 module Data.Map.Strict
68 (
69 -- * Strictness properties
70 -- $strictness
71
72 -- * Map type
73 Map -- instance Eq,Show,Read
74
75 -- * Operators
76 , (!), (!?), (\\)
77
78 -- * Query
79 , null
80 , size
81 , member
82 , notMember
83 , lookup
84 , findWithDefault
85 , lookupLT
86 , lookupGT
87 , lookupLE
88 , lookupGE
89
90 -- * Construction
91 , empty
92 , singleton
93
94 -- ** Insertion
95 , insert
96 , insertWith
97 , insertWithKey
98 , insertLookupWithKey
99
100 -- ** Delete\/Update
101 , delete
102 , adjust
103 , adjustWithKey
104 , update
105 , updateWithKey
106 , updateLookupWithKey
107 , alter
108 , alterF
109
110 -- * Combine
111
112 -- ** Union
113 , union
114 , unionWith
115 , unionWithKey
116 , unions
117 , unionsWith
118
119 -- ** Difference
120 , difference
121 , differenceWith
122 , differenceWithKey
123
124 -- ** Intersection
125 , intersection
126 , intersectionWith
127 , intersectionWithKey
128
129 -- ** General combining functions
130 -- | See "Data.Map.Merge.Strict"
131
132 -- ** Deprecated general combining function
133
134 , mergeWithKey
135
136 -- * Traversal
137 -- ** Map
138 , map
139 , mapWithKey
140 , traverseWithKey
141 , traverseMaybeWithKey
142 , mapAccum
143 , mapAccumWithKey
144 , mapAccumRWithKey
145 , mapKeys
146 , mapKeysWith
147 , mapKeysMonotonic
148
149 -- * Folds
150 , foldr
151 , foldl
152 , foldrWithKey
153 , foldlWithKey
154 , foldMapWithKey
155
156 -- ** Strict folds
157 , foldr'
158 , foldl'
159 , foldrWithKey'
160 , foldlWithKey'
161
162 -- * Conversion
163 , elems
164 , keys
165 , assocs
166 , keysSet
167 , fromSet
168
169 -- ** Lists
170 , toList
171 , fromList
172 , fromListWith
173 , fromListWithKey
174
175 -- ** Ordered lists
176 , toAscList
177 , toDescList
178 , fromAscList
179 , fromAscListWith
180 , fromAscListWithKey
181 , fromDistinctAscList
182 , fromDescList
183 , fromDescListWith
184 , fromDescListWithKey
185 , fromDistinctDescList
186
187 -- * Filter
188 , filter
189 , filterWithKey
190 , restrictKeys
191 , withoutKeys
192 , partition
193 , partitionWithKey
194
195 , takeWhileAntitone
196 , dropWhileAntitone
197 , spanAntitone
198
199 , mapMaybe
200 , mapMaybeWithKey
201 , mapEither
202 , mapEitherWithKey
203
204 , split
205 , splitLookup
206 , splitRoot
207
208 -- * Submap
209 , isSubmapOf, isSubmapOfBy
210 , isProperSubmapOf, isProperSubmapOfBy
211
212 -- * Indexed
213 , lookupIndex
214 , findIndex
215 , elemAt
216 , updateAt
217 , deleteAt
218 , take
219 , drop
220 , splitAt
221
222 -- * Min\/Max
223 , lookupMin
224 , lookupMax
225 , findMin
226 , findMax
227 , deleteMin
228 , deleteMax
229 , deleteFindMin
230 , deleteFindMax
231 , updateMin
232 , updateMax
233 , updateMinWithKey
234 , updateMaxWithKey
235 , minView
236 , maxView
237 , minViewWithKey
238 , maxViewWithKey
239
240 -- * Debugging
241 , showTree
242 , showTreeWith
243 , valid
244 ) where
245
246 import Data.Map.Strict.Internal
247 import Prelude ()
248
249 -- $strictness
250 --
251 -- This module satisfies the following strictness properties:
252 --
253 -- 1. Key arguments are evaluated to WHNF;
254 --
255 -- 2. Keys and values are evaluated to WHNF before they are stored in
256 -- the map.
257 --
258 -- Here's an example illustrating the first property:
259 --
260 -- > delete undefined m == undefined
261 --
262 -- Here are some examples that illustrate the second property:
263 --
264 -- > map (\ v -> undefined) m == undefined -- m is not empty
265 -- > mapKeys (\ k -> undefined) m == undefined -- m is not empty