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