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