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