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