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