Convert to cabal.project
[packages/containers.git] / containers / src / Data / Map / Lazy.hs
1 {-# LANGUAGE CPP #-}
2 #if defined(__GLASGOW_HASKELL__)
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 --
18 -- = Finite Maps (lazy interface)
19 --
20 -- The @'Map' k v@ type represents a finite map (sometimes called a dictionary)
21 -- from keys of type @k@ to values of type @v@. A 'Map' is strict in its keys but lazy
22 -- in its values.
23 --
24 -- The functions in "Data.Map.Strict" are careful to force values before
25 -- installing them in a 'Map'. This is usually more efficient in cases where
26 -- laziness is not essential. The functions in this module do not do so.
27 --
28 -- When deciding if this is the correct data structure to use, consider:
29 --
30 -- * If you are using 'Prelude.Int' keys, you will get much better performance for most
31 -- operations using "Data.IntMap.Lazy".
32 --
33 -- * If you don't care about ordering, consider using @Data.HashMap.Lazy@ from the
34 -- <https://hackage.haskell.org/package/unordered-containers unordered-containers>
35 -- package instead.
36 --
37 -- For a walkthrough of the most commonly used functions see the
38 -- <https://haskell-containers.readthedocs.io/en/latest/map.html maps introduction>.
39 --
40 -- This module is intended to be imported qualified, to avoid name clashes with
41 -- Prelude functions:
42 --
43 -- > import qualified Data.Map.Lazy as Map
44 --
45 -- Note that the implementation is generally /left-biased/. Functions that take
46 -- two maps as arguments and combine them, such as `union` and `intersection`,
47 -- prefer the values in the first argument to those in the second.
48 --
49 --
50 -- == Detailed performance information
51 --
52 -- The amortized running time is given for each operation, with /n/ referring to
53 -- the number of entries in the map.
54 --
55 -- Benchmarks comparing "Data.Map.Lazy" with other dictionary implementations
56 -- can be found at https://github.com/haskell-perf/dictionaries.
57 --
58 --
59 -- == Warning
60 --
61 -- The size of a 'Map' must not exceed @'Prelude.maxBound' :: 'Prelude.Int'@.
62 -- Violation of this condition is not detected and if the size limit is exceeded,
63 -- its behaviour is undefined.
64 --
65 --
66 -- == Implementation
67 --
68 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
69 -- trees of /bounded balance/) as described by:
70 --
71 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
72 -- Journal of Functional Programming 3(4):553-562, October 1993,
73 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
74 -- * J. Nievergelt and E.M. Reingold,
75 -- \"/Binary search trees of bounded balance/\",
76 -- SIAM journal of computing 2(1), March 1973.
77 --
78 -- Bounds for 'union', 'intersection', and 'difference' are as given
79 -- by
80 --
81 -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
82 -- \"/Just Join for Parallel Ordered Sets/\",
83 -- <https://arxiv.org/abs/1602.02120v3>.
84 --
85 -----------------------------------------------------------------------------
86
87 module Data.Map.Lazy (
88 -- * Map type
89 Map -- instance Eq,Show,Read
90
91 -- * Construction
92 , empty
93 , singleton
94 , fromSet
95
96 -- ** From Unordered Lists
97 , fromList
98 , fromListWith
99 , fromListWithKey
100
101 -- ** From Ascending Lists
102 , fromAscList
103 , fromAscListWith
104 , fromAscListWithKey
105 , fromDistinctAscList
106
107 -- ** From Descending Lists
108 , fromDescList
109 , fromDescListWith
110 , fromDescListWithKey
111 , fromDistinctDescList
112
113 -- * Insertion
114 , insert
115 , insertWith
116 , insertWithKey
117 , insertLookupWithKey
118
119 -- * Deletion\/Update
120 , delete
121 , adjust
122 , adjustWithKey
123 , update
124 , updateWithKey
125 , updateLookupWithKey
126 , alter
127 , alterF
128
129 -- * Query
130 -- ** Lookup
131 , lookup
132 , (!?)
133 , (!)
134 , findWithDefault
135 , member
136 , notMember
137 , lookupLT
138 , lookupGT
139 , lookupLE
140 , lookupGE
141
142 -- ** Size
143 , null
144 , size
145
146 -- * Combine
147
148 -- ** Union
149 , union
150 , unionWith
151 , unionWithKey
152 , unions
153 , unionsWith
154
155 -- ** Difference
156 , difference
157 , (\\)
158 , differenceWith
159 , differenceWithKey
160
161 -- ** Intersection
162 , intersection
163 , intersectionWith
164 , intersectionWithKey
165
166 -- ** General combining functions
167 -- | See "Data.Map.Merge.Lazy"
168
169 -- ** Unsafe general combining function
170
171 , mergeWithKey
172
173 -- * Traversal
174 -- ** Map
175 , map
176 , mapWithKey
177 , traverseWithKey
178 , traverseMaybeWithKey
179 , mapAccum
180 , mapAccumWithKey
181 , mapAccumRWithKey
182 , mapKeys
183 , mapKeysWith
184 , mapKeysMonotonic
185
186 -- * Folds
187 , foldr
188 , foldl
189 , foldrWithKey
190 , foldlWithKey
191 , foldMapWithKey
192
193 -- ** Strict folds
194 , foldr'
195 , foldl'
196 , foldrWithKey'
197 , foldlWithKey'
198
199 -- * Conversion
200 , elems
201 , keys
202 , assocs
203 , keysSet
204
205 -- ** Lists
206 , toList
207
208 -- ** Ordered lists
209 , toAscList
210 , toDescList
211
212 -- * Filter
213 , filter
214 , filterWithKey
215 , restrictKeys
216 , withoutKeys
217 , partition
218 , partitionWithKey
219 , takeWhileAntitone
220 , dropWhileAntitone
221 , spanAntitone
222
223 , mapMaybe
224 , mapMaybeWithKey
225 , mapEither
226 , mapEitherWithKey
227
228 , split
229 , splitLookup
230 , splitRoot
231
232 -- * Submap
233 , isSubmapOf, isSubmapOfBy
234 , isProperSubmapOf, isProperSubmapOfBy
235
236 -- * Indexed
237 , lookupIndex
238 , findIndex
239 , elemAt
240 , updateAt
241 , deleteAt
242 , take
243 , drop
244 , splitAt
245
246 -- * Min\/Max
247 , lookupMin
248 , lookupMax
249 , findMin
250 , findMax
251 , deleteMin
252 , deleteMax
253 , deleteFindMin
254 , deleteFindMax
255 , updateMin
256 , updateMax
257 , updateMinWithKey
258 , updateMaxWithKey
259 , minView
260 , maxView
261 , minViewWithKey
262 , maxViewWithKey
263
264 -- * Debugging
265 #ifdef __GLASGOW_HASKELL__
266 , showTree
267 , showTreeWith
268 #endif
269 , valid
270 ) where
271
272 import Data.Map.Internal
273 import Data.Map.Internal.DeprecatedShowTree (showTree, showTreeWith)
274 import Data.Map.Internal.Debug (valid)
275 import Prelude ()