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