2705de5dec27529b1ff9074bc5683fc0f51e7d2e
[packages/containers.git] / Data / Map / Lazy.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && __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 --
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 -- Note that the implementation is /left-biased/ -- the elements of a
44 -- first argument are always preferred to the second, for example in
45 -- 'union' or 'insert'.
46 --
47 -- Operation comments contain the operation time complexity in
48 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
49 -----------------------------------------------------------------------------
50
51 module Data.Map.Lazy (
52 -- * Strictness properties
53 -- $strictness
54
55 -- * Map type
56 #if !defined(TESTING)
57 Map -- instance Eq,Show,Read
58 #else
59 Map(..) -- instance Eq,Show,Read
60 #endif
61
62 -- * Operators
63 , (!), (\\)
64
65 -- * Query
66 , M.null
67 , size
68 , member
69 , notMember
70 , M.lookup
71 , findWithDefault
72 , lookupLT
73 , lookupGT
74 , lookupLE
75 , lookupGE
76
77 -- * Construction
78 , empty
79 , singleton
80
81 -- ** Insertion
82 , insert
83 , insertWith
84 , insertWithKey
85 , insertLookupWithKey
86
87 -- ** Delete\/Update
88 , delete
89 , adjust
90 , adjustWithKey
91 , update
92 , updateWithKey
93 , updateLookupWithKey
94 , alter
95
96 -- * Combine
97
98 -- ** Union
99 , union
100 , unionWith
101 , unionWithKey
102 , unions
103 , unionsWith
104
105 -- ** Difference
106 , difference
107 , differenceWith
108 , differenceWithKey
109
110 -- ** Intersection
111 , intersection
112 , intersectionWith
113 , intersectionWithKey
114
115 -- ** Universal combining function
116 , mergeWithKey
117
118 -- * Traversal
119 -- ** Map
120 , M.map
121 , mapWithKey
122 , traverseWithKey
123 , mapAccum
124 , mapAccumWithKey
125 , mapAccumRWithKey
126 , mapKeys
127 , mapKeysWith
128 , mapKeysMonotonic
129
130 -- * Folds
131 , M.foldr
132 , M.foldl
133 , foldrWithKey
134 , foldlWithKey
135 , foldMapWithKey
136
137 -- ** Strict folds
138 , foldr'
139 , foldl'
140 , foldrWithKey'
141 , foldlWithKey'
142
143 -- * Conversion
144 , elems
145 , keys
146 , assocs
147 , keysSet
148 , fromSet
149
150 -- ** Lists
151 , toList
152 , fromList
153 , fromListWith
154 , fromListWithKey
155
156 -- ** Ordered lists
157 , toAscList
158 , toDescList
159 , fromAscList
160 , fromAscListWith
161 , fromAscListWithKey
162 , fromDistinctAscList
163
164 -- * Filter
165 , M.filter
166 , filterWithKey
167 , partition
168 , partitionWithKey
169
170 , mapMaybe
171 , mapMaybeWithKey
172 , mapEither
173 , mapEitherWithKey
174
175 , split
176 , splitLookup
177 , splitRoot
178
179 -- * Submap
180 , isSubmapOf, isSubmapOfBy
181 , isProperSubmapOf, isProperSubmapOfBy
182
183 -- * Indexed
184 , lookupIndex
185 , findIndex
186 , elemAt
187 , updateAt
188 , deleteAt
189
190 -- * Min\/Max
191 , findMin
192 , findMax
193 , deleteMin
194 , deleteMax
195 , deleteFindMin
196 , deleteFindMax
197 , updateMin
198 , updateMax
199 , updateMinWithKey
200 , updateMaxWithKey
201 , minView
202 , maxView
203 , minViewWithKey
204 , maxViewWithKey
205
206 -- * Debugging
207 , showTree
208 , showTreeWith
209 , valid
210
211 #if defined(TESTING)
212 -- * Internals
213 , bin
214 , balanced
215 , link
216 , merge
217 #endif
218
219 ) where
220
221 import Data.Map.Base as M
222
223 -- $strictness
224 --
225 -- This module satisfies the following strictness property:
226 --
227 -- * Key arguments are evaluated to WHNF
228 --
229 -- Here are some examples that illustrate the property:
230 --
231 -- > insertWith (\ new old -> old) undefined v m == undefined
232 -- > insertWith (\ new old -> old) k undefined m == OK
233 -- > delete undefined m == undefined