Fix Foldable instance for IntMap (fixes #579) (#593)
[packages/containers.git] / changelog.md
1 # Changelog for [`containers` package](http://github.com/haskell/containers)
2
3 ## 0.6.0.2
4
5 * Fix Foldable instance for IntMap, which previously placed positively
6   keyed entries before negatively keyed ones for `fold`, `foldMap`, and
7   `traverse`.
8
9 ## 0.6.0.1
10
11 * Released with GHC 8.6
12
13 ### New functions and class instances
14
15 * Add `Data.Containers.ListUtils` offering `nub`-like functions. (Thanks to
16   Gershom Bazerman for starting the process of writing these.)
17
18 * Add `Generic` and `Generic1` instances for key `Data.Sequence.Internal` types:
19   `Node`, `Digit`, `Elem`, and `FingerTree`.
20
21 ### Death of deprecated functions
22
23 The following functions have been disabled. As an experiment
24 in function removal technology, the functions are still temporarily present,
25 but any attempts to use them will result in type errors advising on
26 replacement.
27
28 * `Data.IntMap`: `insertWith'`, `insertWithKey'`, `fold`, and `foldWithKey`.
29
30 * `Data.Map`: `insertWith'`, `insertWithKey'`, `insertLookupWithKey'`,
31    `fold`, and `foldWithKey`.
32
33 The same has been done for the deprecated exports of `showTree` and
34 `showTreeWith`. These function remain available in the internal `Debug`
35 modules.
36
37 ### Changes to existing functions
38
39 * Generalize the types of `unions` and `unionsWith`. (Thanks, jwaldmann.)
40
41 ### Performance improvements
42
43 * Speed up folds and `traverse` on sequences. (Thanks, Donnacha Oisín Kidney.)
44
45 * Speed up `Data.Set.union`. (Thanks, Joachim Breitner.)
46
47 * Speed up several algorithms in `Data.Graph` a bit by using unboxed arrays
48   where appropriate.
49
50 * Implement `Data.Graph.indegree` directly instead of taking the transpose
51   and calculating its `outdegree`. This may not lead to an immediate performance
52   improvement (see [GHC Trac #14785](https://ghc.haskell.org/trac/ghc/ticket/14785))
53   but it should be better eventually.
54
55 ### Other package changes
56
57 * Drop support for GHC versions before 7.6.
58
59 * Improve `Data.Graph` documentation, and reorganize map and set documentation.
60
61 * Remove the `Data.Map.Lazy.Merge` and `Data.Map.Strict.Merge` modules. These
62   were renamed and deprecated almost as soon as they were introduced.
63
64
65 ## 0.5.11
66
67 * Released with GHC 8.4.
68
69 ### New functions and class instances
70
71 * Add a `MonadFix` instance for `Data.Sequence`.
72
73 * Add a `MonadFix` instance for `Data.Tree`.
74
75 * Add `powerSet`, `cartesianProduct`, and `disjointUnion` for
76   `Data.Set`. (Thanks, Edward Kmett.)
77
78 * Add `disjoint` for `Data.Set` and `Data.IntSet`. (Thanks, Víctor López Juan.)
79
80 * Add `lookupMin` and `lookupMax` to `Data.IntMap`. (Thanks, bwroga.)
81
82 * Add `unzip` and `unzipWith` to `Data.Sequence`. Make unzipping
83   build its results in lockstep to avoid certain space leaks.
84
85 * Add carefully optimized implementations of `sortOn` and `unstableSortOn`
86   to `Data.Sequence`. (Thanks, Donnacha Oisín Kidney.)
87
88 ### Changes to existing functions and features
89
90 * Make `Data.Sequence.replicateM` a synonym for `replicateA`
91   for post-AMP `base`.
92
93 * Rewrite the `IsString` instance head for sequences, improving compatibility
94   with the list instance and also improving type inference. We used to have
95   
96   ```haskell
97   instance IsString (Seq Char)
98   ```
99   
100   Now we commit more eagerly with
101   
102   ```haskell
103   instance a ~ Char => IsString (Seq a)
104   ```
105
106 * Make `>>=` for `Data.Tree` strict in the result of its second argument;
107   being too lazy here is almost useless, and violates one of the monad identity
108   laws. Specifically, `return () >>= \_ -> undefined` should always be
109   `undefined`, but this was not the case.
110
111 * Harmonize laziness details for `minView` and `maxView` between
112   `Data.IntMap` and `Data.Map`.
113
114 ### Performance improvement
115
116 * Speed up both stable and unstable sorting for `Data.Sequence` by (Thanks, Donnacha
117   Oisín Kidney.)
118
119 ### Other changes
120
121 * Update for recent and upcoming GHC and Cabal versions (Thanks, Herbert
122   Valerio Reidel, Simon Jakobi, and Ryan Scott.)
123
124 * Improve external and internal documentation (Thanks, Oleg Grenrus
125   and Benjamin Hodgson.)
126
127 * Add tutorial-style documentation.
128
129 * Add Haddock `@since` annotations for changes made since version
130   0.5.4 (Thanks, Simon Jakobi.)
131
132 * Add a (very incomplete) test suite for `Data.Tree`.
133
134 * Add structural validity checks to the test suites for `Data.IntMap`
135   and `Data.IntSet` (Thanks to Joachim Breitner for catching an error
136   in a first draft.)
137
138 ## 0.5.10.2
139
140 * Released with GHC 8.2.
141
142 * Use `COMPLETE` pragmas to declare complete sets of pattern synonyms
143   for `Data.Sequence`. At last!
144
145 * Make `Data.IntMap.Strict.traverseWithKey` force the values before
146   installing them in the result. Previously, this function could be used to
147   produce an `IntMap` containing undefined values.
148
149 * Fix strictness bugs in various rewrite rules for `Data.Map.Strict` and
150   `Data.IntMap.Strict`. Previously, rules could unintentionally reduce
151   strictness. The most important change in this regard is the elimination
152   of rules rewriting `*.Strict.map coerce` to `coerce`. To map a coercion
153   over a structure for free, be sure to use the lazy `map` or `fmap`.
154   It is possible to write rules that do a somewhat better job of this, but
155   it turns out to be a bit messy.
156
157 * Optimize `Data.IntMap.restrictKeys` and `Data.IntMap.withoutKeys`. The
158   semantic fix in 0.5.10.1 left them rather slow in certain cases.
159
160 * Speed up `size` for `IntSet` and `IntMap` (thanks, Mike Ledger!).
161
162 * Define a custom `liftA2` in `Applicative` instances for base 4.10, and use
163   `liftA2` rather than `<*>` whenever it may be beneficial.
164
165 * Add `liftA2`-related `RULES` for `Data.Sequence`.
166
167 * Export non-deprecated versions of `showTree` and `showTreeWith` from
168   `Data.IntMap.Internal.Debug`.
169
170 ## 0.5.10.1
171
172 * Fix completely incorrect implementations of `Data.IntMap.restrictKeys` and
173   `Data.IntMap.withoutKeys`. Make the tests for these actually run. (Thanks
174   to Tom Smalley for reporting this.)
175   
176 * Fix a minor bug in the `Show1` instance of `Data.Tree`. This produced valid
177   output, but with fewer parentheses than `Show`. (Thanks, Ryan Scott.)
178
179 * Add `MonadZip` instance for `Data.Sequence`.
180
181 * Remove meaningless stability annotations (Thanks, Simon Jakobi.)
182
183 ## 0.5.9.2
184
185 * Backport bug fixes from 0.5.10.1
186
187 ## 0.5.9.1
188
189 * Add `merge` and `mergeA` for `Data.IntMap`.
190
191 * Add instances for `Data.Graph.SCC`: `Foldable`, `Traversable`, `Data`,
192   `Generic`, `Generic1`, `Eq`, `Eq1`, `Show`, `Show1`, `Read`, and `Read1`.
193
194 * Add lifted instances (from `Data.Functor.Classes`) for `Data.Sequence`,
195   `Data.Map`, `Data.Set`, `Data.IntMap`, and `Data.Tree`. (Thanks to
196   Oleg Grenrus for doing a lot of this work.)
197
198 * Properly deprecate functions in `Data.IntMap` long documented as deprecated.
199
200 * Rename several internal modules for clarity. Thanks to esoeylemez for starting
201   this process.
202
203 * Make `Data.Map.fromDistinctAscList` and `Data.Map.fromDistinctDescList` more
204   eager, improving performance.
205
206 * Plug space leaks in `Data.Map.Lazy.fromAscList` and
207  `Data.Map.Lazy.fromDescList` by manually inlining constant functions.
208
209 * Add `lookupMin` and `lookupMax` to `Data.Set` and `Data.Map` as total
210 alternatives to `findMin` and `findMax`.
211
212 * Add `!?` to `Data.Map` as a total alternative to `!`.
213
214 * Avoid using `deleteFindMin` and `deleteFindMax` internally, preferring
215 total functions instead. New implementations of said functions lead to slight
216 performance improvements overall.
217
218 ## 0.5.8.2
219
220 * Backport bug fixes from 0.5.10.1.
221
222 ## 0.5.8.1 *Aug 2016*
223
224 ### General package changes
225
226   * Remove all attempts to support nhc98 and any versions of GHC
227     before 7.0.
228
229   * Integrate benchmarks with Cabal. (Thanks, Gabriel Gonzalez!)
230   
231   * Make Cabal report required extensions properly, and stop using
232     default extensions. Note that we do *not* report extensions conditionally enabled
233     based on GHC version, as doing so would lead to a maintenance nightmare
234     with no obvious benefits.
235
236   * Use `BangPatterns` throughout to reduce noise. This extension
237     is now *required* to compile `containers`.
238
239   * Improve QuickCheck properties taking arbitrary functions by using
240     `Test.QuickCheck.Function.Fun` instead of evil `Show` instances
241     for functions.
242
243   * Expose several internal modules through Cabal (as requested by
244     Edward Kmett). These remain completely unsupported.
245
246 ### New exports and instances
247
248   * Add `alterF`, `restrictKeys`, and `withoutKeys` to `Data.Map`
249     and `Data.IntMap`.
250
251   * Add `take`, `drop`, `splitAt`, `takeWhileAntitone`, `dropWhileAntitone`,
252     and `spanAntitone` for `Data.Map` and `Data.Set`. Thanks to Cale Gibbard
253     for suggesting these.
254
255   * Add `merge`, `mergeA`, and associated merge tactics for `Data.Map`.
256     Many thanks to Cale Gibbard, Ryan Trinkle, and Dan Doel for
257     inspiring the merge idea and helping refine the interface.
258
259   * Add `traverseMaybeWithKey`, `fromDescList`, `fromDescListWith`,
260     `fromDescListWithKey`, and `fromDistinctDescList` to `Data.Map`.
261
262   * Add `fromDescList` and `fromDistinctDescList` to `Data.Set`.
263
264   * Add `Empty`, `:<|`, and `:|>` pattern synonyms for `Data.Sequence`.
265
266   * Add `adjust'`, `(!?)`, `lookup`, `chunksOf`, `cycleTaking`, `insertAt`, `deleteAt`, `intersperse`,
267     `foldMapWithIndex`, and `traverseWithIndex` for `Data.Sequence`.
268
269   * Derive `Generic` and `Generic1` for `Data.Tree.Tree`, `Data.Sequence.ViewL`,
270     and `Data.Sequence.ViewR`.
271
272   * Add `foldTree` for `Data.Tree`. (Thanks, Daniel Wagner!)
273
274 ### Semantic changes
275
276   * Make `Data.Sequence.splitAt` strict in its arguments. Previously,
277     it returned a lazy pair.
278
279   * Fix completely erroneous definition of `length` for `Data.Sequence.ViewR`.
280   
281   * Make `Data.Map.Strict.traverseWithKey` force result values before
282     installing them in the new map.
283
284   * Make `drawTree` handle newlines better. (Thanks, recursion-ninja!)
285
286 ### Deprecations
287
288   * All functions in `Data.Map` proper that have been documented as deprecated since
289     version 0.5 or before now have `DEPRECATED` pragmas and will actually be
290     removed after another cycle or two.
291
292   * Tree printing functions in `Data.Map` intended for library debugging are now
293     deprecated. They will continue to be available for the foreseeable future in
294     an internal module.
295
296 ### Performance changes
297
298   * Substantially speed up `splitAt`, `zipWith`, `take`, `drop`,
299     `fromList`, `partition`, `foldl'`, and `foldr'` for `Data.Sequence`.
300     Special thanks to Lennart Spitzner for digging into the performance
301     problems with previous versions of `fromList` and finding a way to
302     make it really fast. Slightly optimize `replicateA`. Stop `traverse`
303     from performing many unnecessary `fmap` operations.
304
305   * Most operations in `Data.Sequence` advertised as taking logarithmic
306     time (including `><` and `adjust`) now use their full allotted time
307     to avoid potentially building up chains of thunks in the tree. In general,
308     the only remaining operations that avoid doing more than they
309     really need are the particular bulk creation and transformation functions
310     that really benefit from the extra laziness. There are some situations
311     where this change may slow programs down, but I think having more
312     predictable and usually better performance more than makes up for that.
313
314   * Add rewrite rules to fuse `fmap` with `reverse` for `Data.Sequence`.
315
316   * Switch from *hedge* algorithms to *divide-and-conquer* algorithms
317     for union, intersection, difference, and merge in both `Data.Map`
318     and `Data.Set`. These algorithms are simpler, are known to be
319     asymptotically optimal, and are faster according to our benchmarks.
320
321   * Speed up `adjust` for `Data.Map`. Allow `map` to inline, and
322     define a custom `(<$)`. This considerably improves mapping with
323     a constant function.
324
325   * Remove non-essential laziness in `Data.Map.Lazy` implementation.
326
327   * Speed up deletion and alteration functions for `Data.IntMap`.
328
329
330 ## 0.5.7.1  *Dec 2015*
331
332   * Planned to bundle with GHC 8.0.1.
333
334   * Add `IsString` instance to `Data.Sequence`.
335
336   * Define `Semigroup` instances for `Data.Map`, `Data.Set`, `Data.IntMap`,
337     `Data.IntSet` and `Data.Sequence`.
338
339 ## 0.5.6.2  *Dec 2014*
340
341   * Bundled with GHC 7.10.1.
342
343   * Add role annotations for `Data.Map` and `Data.Set`.
344
345   * Add `IsList` instances for `Data.Map`, `Data.Set`, `Data.IntMap` and
346     `Data.IntSet`.
347
348   * Several performance improvements for `Data.Sequence`.
349
350   * Add `Data.Sequence.fromFunction` and `Data.Sequence.fromArray`.
351
352 ## 0.5.4.0  *Jan 2014*
353
354   * Bundled with GHC 7.8.1.
355
356   * The `Data.Map.fromList` and `Data.Set.fromList` now use linear-time
357     algorithm if the input is sorted, without need to call `fromDistinctAscList`.
358
359   * Implement indexing operations (`lookupIndex`, `findIndex`, `elemAt`,
360     `deletaAt`) for `Data.Set` too.
361
362   * Add `Applicative` and `Alternative` instances for `Data.Sequence`.
363
364   * Add `foldMapWithKey` to `Data.Map` and `Data.IntMap`.
365
366   * Implement poly-kinded `Typeable`.
367
368   * Add `Functor` instance for `Data.Graph.SCC`.
369
370   * Add `Data.Map.splitRoot` and `Data.Set.splitRoot`.
371
372 ## 0.5.0.0  *May 2012*
373
374   * Bundled with GHC 7.6.1.
375
376   * Major improvements since last release:
377     * a clearer distinction between value-lazy and value-strict containers,
378     * performance improvements across the board,
379     * a big internal clean-up, and
380     * new functions for e.g. merging, updating, and searching containers.
381
382   * While the old `Data.Map` and
383     `Data.IntMap` modules will continue to exist for the foreseeable future, we've
384     abandoned the practice of having the strict and lazy versions of each
385     function distinguished by an apostrophe. The distinction is instead made at
386     the module level, by introducing four new modules:
387     * Data.Map.Strict
388     * Data.Map.Lazy
389     * Data.IntMap.Strict
390     * Data.IntMap.Lazy
391
392     This split has three benefits:
393     * It makes the choice between value-strict and value-lazy containers
394       more declarative; you pick once at import time, instead of having to
395       remember to use the strict or lazy versions of a function every time
396       you modify the container.
397     * It alleviates a common source of performance issues, by forcing the
398       user to think about the strictness properties upfront. For example,
399       using insertWith instead of insertWith' is a common source of
400       containers-related performance bugs.
401     * There are fewer functions per module, making it easier to get an
402       overview of each module.
403
404   * Note that the types used in the strict and lazy APIs are the same, so
405     you can still use the same container in a "mixed" manner, if needed.
406
407   * The `Data.IntSet` representation changed to store small sets using
408     bits in an `Word`. Larger sets are stored as a collection of such
409     dense small sets, connected together by a prefix trie.
410
411 ## 0.4.2.1  *Feb 2012*
412
413   * Bundled with GHC 7.4.1.
414
415   * `Data.Map now exports `foldr`, `foldr'`, `foldl` and `foldl'`.
416
417   * `Data.Set now exports `foldr`, `foldr'`, `foldl` and `foldl'`.
418
419   * `Data.IntMap now exports `foldr`, `foldr'`, `foldl`, `foldl'`, `foldrWithKey`, `foldrWithKey'`, `foldlWithKey` and `foldlWithKey'`.
420
421   * `Data.IntSet now exports `foldr`, `foldr'`, `foldl` and `foldl'`.
422
423   * `Data.Map.foldWithKey` is no longer deprecated, although it is expected to be deprecated again in the future.
424
425   * There are now `NFData` instance for `Data.Map.Map`, `Data.Set.Set`, `Data.IntMap.IntMap`, `Data.IntSet.IntSet` and `Data.Tree.Tree`.
426
427 ## 0.4.1.0  *Aug 2011*
428
429   * Bundled with GHC 7.2.1.
430
431   * `Data.Map` now exports new functions `foldrWithKey'` and `foldlWithKey'`, which are strict variants of `foldrWithKey` and `foldlWithKey` respectively.
432
433   * `Data.IntMap` now exports new functions `insertWith'` and `insertWithKey'`, which are strict variants of `insertWith` and `insertWithKey` respectively.
434
435 ## 0.4.0.0  *Nov 2010*
436
437   * Bundled with GHC 7.0.1.
438
439   * Strictness is now more consistent, with containers being strict in their elements even in singleton cases.
440
441   * There is a new function `insertLookupWithKey'` in `Data.Map`.
442
443   * The `foldWithKey` function in `Data.Map` has been deprecated in favour of `foldrWithKey`.
444
445 ## 0.3.0.0  *Dec 2009*
446
447   * Bundled with GHC 6.12.1.
448
449   * `mapAccumRWithKey` has been added to `Data.IntMap`.
450
451   * A `Traversable` instance has been added to `Data.IntMap.IntMap`.
452
453   * The types of `Data.IntMap.intersectionWith` and `Data.IntMap.intersectionWithKey` have been changed from
454     `intersectionWith :: (a -> b -> a) -> IntMap a -> IntMap b -> IntMap a`
455     `intersectionWithKey :: (Key -> a -> b -> a) -> IntMap a -> IntMap b -> IntMap a`
456     to
457     `intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c`
458     `intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c`
459
460   * The types of `Data.IntMap.findMin` and `Data.IntMap.findMax` have been changed from
461     `findMin :: IntMap a -> a`
462     `findMax :: IntMap a -> a`
463     to
464     `findMin :: IntMap a -> (Int,a)`
465     `findMax :: IntMap a -> (Int,a)`
466
467   * `Data.Map` now exports `mapAccumRWithKey`, `foldrWithKey`, `foldlWithKey` and `toDescList`.
468
469   * `Data.Sequence` now exports `replicate`, `replicateA`, `replicateM`, `iterateN`, `unfoldr`, `unfoldl`, `scanl`, `scanl1`, `scanr`, `scanr1`, `tails`, `inits`, `takeWhileL`, `takeWhileR`, `dropWhileL`, `dropWhileR`, `spanl`, `spanr`, `breakl`, `breakr`, `partition`, `filter`, `sort`, `sortBy`, `unstableSort`, `unstableSortBy`, `elemIndexL`, `elemIndicesL`, `elemIndexR`, `elemIndicesR`, `findIndexL`, `findIndicesL`, `findIndexR`, `findIndicesR`, `foldlWithIndex`, `foldrWithIndex`, `mapWithIndex`, `zip`, `zipWith`, `zip3`, `zipWith3`, `zip4` and `zipWith4`.
470
471 ## 0.2.0.0  *Nov 2008*
472
473   * Bundled with GHC 6.10.1.
474
475   * Various result type now use `Maybe` rather than allowing any `Monad`.
476
477 ## 0.1.0.0  *Nov 2007*
478
479   * Bundled with GHC 6.8.1.
480
481   * Initial split off from GHC base.