4f3e25fea2c8ec6f5638a784ac394c5f8a883b79
[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 -- Stability : provisional
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 the keys, but lazy in the values.
22 -- If you need value-strict maps, use "Data.Map.Strict" instead.
23 -- The 'Map' type itself 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.Lazy 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
61 module Data.Map.Lazy (
62 -- * Strictness properties
63 -- $strictness
64
65 -- * Map type
66 Map -- instance Eq,Show,Read
67
68 -- * Operators
69 , (!), (\\)
70
71 -- * Query
72 , M.null
73 , size
74 , member
75 , notMember
76 , M.lookup
77 , findWithDefault
78 , lookupLT
79 , lookupGT
80 , lookupLE
81 , lookupGE
82
83 -- * Construction
84 , empty
85 , singleton
86
87 -- ** Insertion
88 , insert
89 , insertWith
90 , insertWithKey
91 , insertLookupWithKey
92
93 -- ** Delete\/Update
94 , delete
95 , adjust
96 , adjustWithKey
97 , update
98 , updateWithKey
99 , updateLookupWithKey
100 , alter
101 , alterF
102
103 -- * Combine
104
105 -- ** Union
106 , union
107 , unionWith
108 , unionWithKey
109 , unions
110 , unionsWith
111
112 -- ** Difference
113 , difference
114 , differenceWith
115 , differenceWithKey
116
117 -- ** Intersection
118 , intersection
119 , intersectionWith
120 , intersectionWithKey
121
122 -- ** General combining functions
123 -- | See "Data.Map.Lazy.Merge"
124
125 -- ** Unsafe general combining function
126
127 , mergeWithKey
128
129 -- * Traversal
130 -- ** Map
131 , M.map
132 , mapWithKey
133 , traverseWithKey
134 , traverseMaybeWithKey
135 , mapAccum
136 , mapAccumWithKey
137 , mapAccumRWithKey
138 , mapKeys
139 , mapKeysWith
140 , mapKeysMonotonic
141
142 -- * Folds
143 , M.foldr
144 , M.foldl
145 , foldrWithKey
146 , foldlWithKey
147 , foldMapWithKey
148
149 -- ** Strict folds
150 , foldr'
151 , foldl'
152 , foldrWithKey'
153 , foldlWithKey'
154
155 -- * Conversion
156 , elems
157 , keys
158 , assocs
159 , keysSet
160 , fromSet
161
162 -- ** Lists
163 , toList
164 , fromList
165 , fromListWith
166 , fromListWithKey
167
168 -- ** Ordered lists
169 , toAscList
170 , toDescList
171 , fromAscList
172 , fromAscListWith
173 , fromAscListWithKey
174 , fromDistinctAscList
175 , fromDescList
176 , fromDescListWith
177 , fromDescListWithKey
178 , fromDistinctDescList
179
180 -- * Filter
181 , M.filter
182 , filterWithKey
183 , restrictKeys
184 , withoutKeys
185 , partition
186 , partitionWithKey
187 , takeWhileAntitone
188 , dropWhileAntitone
189 , spanAntitone
190
191 , mapMaybe
192 , mapMaybeWithKey
193 , mapEither
194 , mapEitherWithKey
195
196 , split
197 , splitLookup
198 , splitRoot
199
200 -- * Submap
201 , isSubmapOf, isSubmapOfBy
202 , isProperSubmapOf, isProperSubmapOfBy
203
204 -- * Indexed
205 , lookupIndex
206 , findIndex
207 , elemAt
208 , updateAt
209 , deleteAt
210 , take
211 , drop
212 , splitAt
213
214 -- * Min\/Max
215 , findMin
216 , findMax
217 , deleteMin
218 , deleteMax
219 , deleteFindMin
220 , deleteFindMax
221 , updateMin
222 , updateMax
223 , updateMinWithKey
224 , updateMaxWithKey
225 , minView
226 , maxView
227 , minViewWithKey
228 , maxViewWithKey
229
230 -- * Debugging
231 , showTree
232 , showTreeWith
233 , valid
234 ) where
235
236 import Data.Map.Base as M
237 import Prelude ()
238
239 -- $strictness
240 --
241 -- This module satisfies the following strictness property:
242 --
243 -- * Key arguments are evaluated to WHNF
244 --
245 -- Here are some examples that illustrate the property:
246 --
247 -- > insertWith (\ new old -> old) undefined v m == undefined
248 -- > insertWith (\ new old -> old) k undefined m == OK
249 -- > delete undefined m == undefined