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