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