Document the Semigroup for Map
[packages/containers.git] / Data / IntMap / Lazy.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
3 {-# LANGUAGE Safe #-}
4 #endif
5
6 #include "containers.h"
7
8 -----------------------------------------------------------------------------
9 -- |
10 -- Module : Data.IntMap.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 Int Maps (lazy interface)
19 --
20 -- The @'IntMap' v@ type represents a finite map (sometimes called a dictionary)
21 -- from keys of type @Int@ to values of type @v@.
22 --
23 -- The functions in "Data.IntMap.Strict" are careful to force values before
24 -- installing them in an 'IntMap'. This is usually more efficient in cases where
25 -- laziness is not essential. The functions in this module do not do so.
26 --
27 -- For a walkthrough of the most commonly used functions see the
28 -- <https://haskell-containers.readthedocs.io/en/latest/map.html maps introduction>.
29 --
30 -- This module is intended to be imported qualified, to avoid name clashes with
31 -- Prelude functions:
32 --
33 -- > import Data.IntMap.Lazy (IntMap)
34 -- > import qualified Data.IntMap.Lazy as IntMap
35 --
36 -- Note that the implementation is generally /left-biased/. Functions that take
37 -- two maps as arguments and combine them, such as `union` and `intersection`,
38 -- prefer the values in the first argument to those in the second.
39 --
40 --
41 -- == Detailed performance information
42 --
43 -- The amortized running time is given for each operation, with /n/ referring to
44 -- the number of entries in the map and /W/ referring to the number of bits in
45 -- an 'Int' (32 or 64).
46 --
47 -- Benchmarks comparing "Data.IntMap.Lazy" with other dictionary
48 -- implementations can be found at https://github.com/haskell-perf/dictionaries.
49 --
50 --
51 -- == Implementation
52 --
53 -- The implementation is based on /big-endian patricia trees/. This data
54 -- structure performs especially well on binary operations like 'union' and
55 -- 'intersection'. Additionally, benchmarks show that it is also (much) faster
56 -- on insertions and deletions when compared to a generic size-balanced map
57 -- implementation (see "Data.Map").
58 --
59 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
60 -- Workshop on ML, September 1998, pages 77-86,
61 -- <http://citeseer.ist.psu.edu/okasaki98fast.html>
62 --
63 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
64 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
65 -- October 1968, pages 514-534.
66 --
67 -----------------------------------------------------------------------------
68
69 module Data.IntMap.Lazy (
70 -- * Map type
71 #if !defined(TESTING)
72 IntMap, Key -- instance Eq,Show
73 #else
74 IntMap(..), Key -- instance Eq,Show
75 #endif
76
77 -- * Construction
78 , empty
79 , singleton
80 , fromSet
81
82 -- ** From Unordered Lists
83 , fromList
84 , fromListWith
85 , fromListWithKey
86
87 -- ** From Ascending Lists
88 , fromAscList
89 , fromAscListWith
90 , fromAscListWithKey
91 , fromDistinctAscList
92
93 -- * Insertion
94 , insert
95 , insertWith
96 , insertWithKey
97 , insertLookupWithKey
98
99 -- * Deletion\/Update
100 , delete
101 , adjust
102 , adjustWithKey
103 , update
104 , updateWithKey
105 , updateLookupWithKey
106 , alter
107 , alterF
108
109 -- * Query
110 -- ** Lookup
111 , IM.lookup
112 , (!?)
113 , (!)
114 , findWithDefault
115 , member
116 , notMember
117 , lookupLT
118 , lookupGT
119 , lookupLE
120 , lookupGE
121
122 -- ** Size
123 , IM.null
124 , size
125
126 -- * Combine
127
128 -- ** Union
129 , union
130 , unionWith
131 , unionWithKey
132 , unions
133 , unionsWith
134
135 -- ** Difference
136 , difference
137 , (\\)
138 , differenceWith
139 , differenceWithKey
140
141 -- ** Intersection
142 , intersection
143 , intersectionWith
144 , intersectionWithKey
145
146 -- ** Universal combining function
147 , mergeWithKey
148
149 -- * Traversal
150 -- ** Map
151 , IM.map
152 , mapWithKey
153 , traverseWithKey
154 , mapAccum
155 , mapAccumWithKey
156 , mapAccumRWithKey
157 , mapKeys
158 , mapKeysWith
159 , mapKeysMonotonic
160
161 -- * Folds
162 , IM.foldr
163 , IM.foldl
164 , foldrWithKey
165 , foldlWithKey
166 , foldMapWithKey
167
168 -- ** Strict folds
169 , foldr'
170 , foldl'
171 , foldrWithKey'
172 , foldlWithKey'
173
174 -- * Conversion
175 , elems
176 , keys
177 , assocs
178 , keysSet
179
180 -- ** Lists
181 , toList
182
183 -- ** Ordered lists
184 , toAscList
185 , toDescList
186
187 -- * Filter
188 , IM.filter
189 , filterWithKey
190 , restrictKeys
191 , withoutKeys
192 , partition
193 , partitionWithKey
194
195 , mapMaybe
196 , mapMaybeWithKey
197 , mapEither
198 , mapEitherWithKey
199
200 , split
201 , splitLookup
202 , splitRoot
203
204 -- * Submap
205 , isSubmapOf, isSubmapOfBy
206 , isProperSubmapOf, isProperSubmapOfBy
207
208 -- * Min\/Max
209 , lookupMin
210 , lookupMax
211 , findMin
212 , findMax
213 , deleteMin
214 , deleteMax
215 , deleteFindMin
216 , deleteFindMax
217 , updateMin
218 , updateMax
219 , updateMinWithKey
220 , updateMaxWithKey
221 , minView
222 , maxView
223 , minViewWithKey
224 , maxViewWithKey
225
226 #ifdef __GLASGOW_HASKELL__
227 -- * Debugging
228 , showTree
229 , showTreeWith
230 #endif
231 ) where
232
233 import Data.IntMap.Internal as IM hiding (showTree, showTreeWith)
234 #ifdef __GLASGOW_HASKELL__
235 import Data.IntMap.Internal.DeprecatedDebug
236 #endif