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