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