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