Write custom strict folds (#281)
[packages/containers.git] / changelog.md
1 # Changelog for [`containers` package](http://github.com/haskell/containers)
2
3 ## 0.5.8.1
4
5   * Remove all attempts to support nhc98 and any versions of GHC
6     before 7.0.
7
8   * Integrate benchmarks with Cabal. (Thanks, Gabriel Gonzalez!)
9   
10   * Make Cabal report required extensions properly, and stop using
11     default extensions. Note that we do *not* report extensions conditionally enabled
12     based on GHC version, as doing so would lead to a maintenance nightmare
13     with no obvious benefits.
14
15   * Use `BangPatterns` throughout to reduce noise. This extension
16     is now *required* to compile `containers`.
17
18   * Add `alterF` for `Data.Map` and `Data.IntMap`.
19
20   * Make `Data.Map.Strict.traverseWithKey` force result values before
21     installing them in the new map.
22
23   * Add `Empty`, `:<|`, and `:|>` pattern synonyms for `Data.Sequence`.
24
25   * Add (!?), `lookup`, `chunksOf`, `cycleTaking`, `insertAt`, `deleteAt`, `intersperse`,
26     `foldMapWithIndex`, and `traverseWithIndex` for `Data.Sequence`.
27
28   * Make `splitAt` in `Data.Sequence` strict in its arguments. Previously,
29     it returned a lazy pair.
30
31   * Fix completely erroneous definition of `length` for `ViewR`.
32
33   * Derive `Generic` and `Generic1` for `Data.Tree`.
34
35   * Add `foldTree` for `Data.Tree`.
36
37   * Slightly optimize `replicateA` and `traverse` for `Data.Sequence`.
38   
39   * Substantially speed up `splitAt` and (consequently) `zipWith` for
40     `Data.Sequence` by building the result sequences eagerly and rearranging
41     code to avoid allocating unnecessary intermediate structures. The
42     improvements are greatest for small sequences, but large even for long
43     ones. Reimplement `take` and `drop` to avoid building trees only to discard them.
44
45   * Roughly double the speeds of `foldl'` and `foldr'` for `Data.Sequence`
46     by writing custom definitions instead of using the defaults.
47
48   * Add rewrite rules to fuse `fmap` with `reverse` for `Data.Sequence`.
49
50   * Speed up `adjust` for `Data.Map`.
51
52   * Remove non-essential laziness in `Data.Map.Lazy` implementation.
53
54   * Speed up deletion and alteration functions for `Data.IntMap`.
55
56   * Improve QuickCheck properties taking arbitrary functions by using
57     `Test.QuickCheck.Function.Fun` instead of evil `Show` instances
58     for functions.
59
60 ## 0.5.7.1  *Dec 2015*
61
62   * Planned to bundle with GHC 8.0.1.
63
64   * Add `IsString` instance to `Data.Sequence`.
65
66   * Define `Semigroup` instances for `Data.Map`, `Data.Set`, `Data.IntMap`,
67     `Data.IntSet` and `Data.Sequence`.
68
69 ## 0.5.6.2  *Dec 2014*
70
71   * Bundled with GHC 7.10.1.
72
73   * Add role annotations for `Data.Map` and `Data.Set`.
74
75   * Add `IsList` instances for `Data.Map`, `Data.Set`, `Data.IntMap` and
76     `Data.IntSet`.
77
78   * Several performance improvements for `Data.Sequence`.
79
80   * Add `Data.Sequence.fromFunction` and `Data.Sequence.fromArray`.
81
82 ## 0.5.4.0  *Jan 2014*
83
84   * Bundled with GHC 7.8.1.
85
86   * The `Data.Map.fromList` and `Data.Set.fromList` now use linear-time
87     algorithm if the input is sorted, without need to call `fromDistinctAscList`.
88
89   * Implement indexing operations (`lookupIndex`, `findIndex`, `elemAt`,
90     `deletaAt`) for `Data.Set` too.
91
92   * Add `Applicative` and `Alternative` instances for `Data.Sequence`.
93
94   * Add `foldMapWithKey` to `Data.Map` and `Data.IntMap`.
95
96   * Implement poly-kinded `Typeable`.
97
98   * Add `Functor` instance for `Data.Graph.SCC`.
99
100   * Add `Data.Map.splitRoot` and `Data.Set.splitRoot`.
101
102 ## 0.5.0.0  *May 2012*
103
104   * Bundled with GHC 7.6.1.
105
106   * Major improvements since last release:
107     * a clearer distinction between value-lazy and value-strict containers,
108     * performance improvements across the board,
109     * a big internal clean-up, and
110     * new functions for e.g. merging, updating, and searching containers.
111
112   * While the old `Data.Map` and
113     `Data.IntMap` modules will continue to exist for the foreseeable future, we've
114     abandoned the practice of having the strict and lazy versions of each
115     function distinguished by an apostrophe. The distinction is instead made at
116     the module level, by introducing four new modules:
117     * Data.Map.Strict
118     * Data.Map.Lazy
119     * Data.IntMap.Strict
120     * Data.IntMap.Lazy
121
122     This split has three benefits:
123     * It makes the choice between value-strict and value-lazy containers
124       more declarative; you pick once at import time, instead of having to
125       remember to use the strict or lazy versions of a function every time
126       you modify the container.
127     * It alleviates a common source of performance issues, by forcing the
128       user to think about the strictness properties upfront. For example,
129       using insertWith instead of insertWith' is a common source of
130       containers-related performance bugs.
131     * There are fewer functions per module, making it easier to get an
132       overview of each module.
133
134   * Note that the types used in the strict and lazy APIs are the same, so
135     you can still use the same container in a "mixed" manner, if needed.
136
137   * The `Data.IntSet` representation changed to store small sets using
138     bits in an `Word`. Larger sets are stored as a collection of such
139     dense small sets, connected together by a prefix trie.
140
141 ## 0.4.2.1  *Feb 2012*
142
143   * Bundled with GHC 7.4.1.
144
145   * `Data.Map now exports `foldr`, `foldr'`, `foldl` and `foldl'`.
146
147   * `Data.Set now exports `foldr`, `foldr'`, `foldl` and `foldl'`.
148
149   * `Data.IntMap now exports `foldr`, `foldr'`, `foldl`, `foldl'`, `foldrWithKey`, `foldrWithKey'`, `foldlWithKey` and `foldlWithKey'`.
150
151   * `Data.IntSet now exports `foldr`, `foldr'`, `foldl` and `foldl'`.
152
153   * `Data.Map.foldWithKey` is no longer deprecated, although it is expected to be deprecated again in the future.
154
155   * There are now `NFData` instance for `Data.Map.Map`, `Data.Set.Set`, `Data.IntMap.IntMap`, `Data.IntSet.IntSet` and `Data.Tree.Tree`.
156
157 ## 0.4.1.0  *Aug 2011*
158
159   * Bundled with GHC 7.2.1.
160
161   * `Data.Map` now exports new functions `foldrWithKey'` and `foldlWithKey'`, which are strict variants of `foldrWithKey` and `foldlWithKey` respectively.
162
163   * `Data.IntMap` now exports new functions `insertWith'` and `insertWithKey'`, which are strict variants of `insertWith` and `insertWithKey` respectively.
164
165 ## 0.4.0.0  *Nov 2010*
166
167   * Bundled with GHC 7.0.1.
168
169   * Strictness is now more consistent, with containers being strict in their elements even in singleton cases.
170
171   * There is a new function `insertLookupWithKey'` in `Data.Map`.
172
173   * The `foldWithKey` function in `Data.Map` has been deprecated in favour of `foldrWithKey`.
174
175 ## 0.3.0.0  *Dec 2009*
176
177   * Bundled with GHC 6.12.1.
178
179   * `mapAccumRWithKey` has been added to `Data.IntMap`.
180
181   * A `Traversable` instance has been added to `Data.IntMap.IntMap`.
182
183   * The types of `Data.IntMap.intersectionWith` and `Data.IntMap.intersectionWithKey` have been changed from
184     `intersectionWith :: (a -> b -> a) -> IntMap a -> IntMap b -> IntMap a`
185     `intersectionWithKey :: (Key -> a -> b -> a) -> IntMap a -> IntMap b -> IntMap a`
186     to
187     `intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c`
188     `intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c`
189
190   * The types of `Data.IntMap.findMin` and `Data.IntMap.findMax` have been changed from
191     `findMin :: IntMap a -> a`
192     `findMax :: IntMap a -> a`
193     to
194     `findMin :: IntMap a -> (Int,a)`
195     `findMax :: IntMap a -> (Int,a)`
196
197   * `Data.Map` now exports `mapAccumRWithKey`, `foldrWithKey`, `foldlWithKey` and `toDescList`.
198
199   * `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`.
200
201 ## 0.2.0.0  *Nov 2008*
202
203   * Bundled with GHC 6.10.1.
204
205   * Various result type now use `Maybe` rather than allowing any `Monad`.
206
207 ## 0.1.0.0  *Nov 2007*
208
209   * Bundled with GHC 6.8.1.
210
211   * Initial split off from GHC base.