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