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