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