Ticket #5034: improve-performance-of-data_graph_.dpatch

1 patch for repository http://darcs.haskell.org/packages/containers:

Fri Mar 18 21:05:31 CET 2011  Michal Terepeta <michal.terepeta@gmail.com>
  * Improve performance of Data.Graph.

New patches:

[Improve performance of Data.Graph.
Michal Terepeta <michal.terepeta@gmail.com>**20110318200531
 Ignore-this: 38b88943394c53b3d4c7809f28e5e5c1
] {
hunk ./Data/Graph.hs 71
 import Data.Maybe
 import Data.Array
 import Data.List
+import qualified Data.Sequence as S
+import qualified Data.Foldable as F
+
 
 -------------------------------------------------------------------------
 --                                                                     -
hunk ./Data/Graph.hs 322
 -- Algorithm 1: depth first search numbering
 ------------------------------------------------------------
 
-preorder            :: Tree a -> [a]
-preorder (Node a ts) = a : preorderF ts
-
-preorderF           :: Forest a -> [a]
-preorderF ts         = concat (map preorder ts)
+preorderF :: Forest a -> [a]
+preorderF = F.toList . go
+  where
+    go []              = S.empty
+    go (Node a f:rest) = a S.<| go f S.>< go rest
 
 tabulate        :: Bounds -> [Vertex] -> Table Int
 tabulate bnds vs = array bnds (zipWith (,) vs [1..])
hunk ./Data/Graph.hs 338
 -- Algorithm 2: topological sorting
 ------------------------------------------------------------
 
-postorder :: Tree a -> [a]
-postorder (Node a ts) = postorderF ts ++ [a]
-
-postorderF   :: Forest a -> [a]
-postorderF ts = concat (map postorder ts)
+postorderF :: Forest a -> [a]
+postorderF = F.toList . go
+  where
+    go []              = S.empty
+    go (Node a f:rest) = go f S.>< S.singleton a S.>< go rest
 
 postOrd      :: Graph -> [Vertex]
 postOrd       = postorderF . dff
}

Context:

[spell out fmap definitions instead of using fmapDefault
Ross Paterson <ross@soi.city.ac.uk>**20110224011407
 Ignore-this: 1b01d4e4bc397c5c6a1198fab2111573
] 
[add split/append benchmark for Data.Sequence
Ross Paterson <ross@soi.city.ac.uk>**20110202011606
 Ignore-this: 59ceb723663e2021c99bbed46c90db58
] 
[add -rtsopts (needed to use +RTS with GHC-7.0)
Ross Paterson <ross@soi.city.ac.uk>**20110202011346
 Ignore-this: ebbbf7639a3b80a954366ca1b9507568
] 
[remove __HADDOCK__ ifdefs
Ross Paterson <ross@soi.city.ac.uk>**20110115121344
 Ignore-this: 9f638c4f603629645e987188d63585d0
] 
[tweak indentation (whitespace only)
Ross Paterson <ross@soi.city.ac.uk>**20110115120510
 Ignore-this: 439b3001e762c6adad07070897a58d01
] 
[QuickCheck properties for Data.Sequence
Ross Paterson <ross@soi.city.ac.uk>**20110115011403
 Ignore-this: 621e327003e9777fcb874e18598c9903
] 
[tweak indentation (whitespace only)
Ross Paterson <ross@soi.city.ac.uk>**20110115010705
 Ignore-this: 2bf00adf8960a983fa782102680de4b8
] 
[more fine-grained tests
Ross Paterson <ross@soi.city.ac.uk>**20110114100642
 Ignore-this: 23a04888564cdf415e681bdcdb4e1b51
 
 Distinguish between whether the key searched for is present or not,
 and the different uses of update and alter.
] 
[Fixed space leak in lookupIndex
Johan Tibell <johan.tibell@gmail.com>**20110109113222
 Ignore-this: 4fcd3af4b613a1cdfd306bb9708a5eaa
] 
[Rollback "hoist constant parameter"
Johan Tibell <johan.tibell@gmail.com>**20110109112457
 Ignore-this: ecb77a93588ca5743273cf777ce73826
 
 SAT-ing the key causes an extra closure to be allocated.
 
 rolling back:
 
 Fri Jan  7 16:50:12 CET 2011  Ross Paterson <ross@soi.city.ac.uk>
   * hoist constant parameter
 
     M ./Data/Map.hs -8 +7
] 
[hoist constant parameter
Ross Paterson <ross@soi.city.ac.uk>**20110107155012
 Ignore-this: 1061fdf82eb91cad409ccea022610856
] 
[fix typos in comments
Ross Paterson <ross@soi.city.ac.uk>**20101215172553
 Ignore-this: f66f871ce348a41bc1598bc2b5e40943
] 
[whitespace changes and a little re-ordering to make the export lists match
Ross Paterson <ross@soi.city.ac.uk>**20101215170649
 Ignore-this: 3bf7b6d824ea1c25ed92bbe3ca826efe
] 
[whitespace changes and a little re-ordering to make the export lists match
Ross Paterson <ross@soi.city.ac.uk>**20101215162127
 Ignore-this: 7f11aef6c6c8330bb93b6571589e18af
] 
[change Int to Key (type synonym) in 3 places for consistency
Ross Paterson <ross@soi.city.ac.uk>**20101215150459
 Ignore-this: 6da6f8629bb0718e2394a85ce0944d7f
] 
[use Applicative form in Arbitrary instances
Ross Paterson <ross@soi.city.ac.uk>**20101213040129
 Ignore-this: 335e6eac24563baef481fdc689f369dc
 (these are ifdef'ed out by default)
] 
[fix comment for unfoldl
Ross Paterson <ross@soi.city.ac.uk>**20101213040022
 Ignore-this: c4bac18538933b981ed2875595f98196
] 
[make local binding monomorphic without using scoped type variables
Ross Paterson <ross@soi.city.ac.uk>**20101213035831
 Ignore-this: 52b7f5ed7cb7c6ef0eda6caa39e4713f
] 
[Always inline foldrWithKey' and foldlWithKey' from Data.Map
Johan Tibell <johan.tibell@gmail.com>**20101201110527
 Ignore-this: a84198febd304659ff029c3424855be3
 
 Inlining makes it possible to replace an indirect call to an unknown
 function with a call to a known function at the call site.
] 
[Tweak insertWith' and insertWithKey' to better match the non-' versions
Ian Lynagh <igloo@earth.li>**20101128175028
 Ignore-this: 41b50b13b1a94ae56bad8d381c696d04
 They now are not marked inlinable, force the key, and are exported.
] 
[Add foldlWithKey' and foldrWithKey' to Data.Map
Johan Tibell <johan.tibell@gmail.com>**20101103132836
 Ignore-this: d2ac0f0a50842ec5a007b9ad11ce63d0
] 
[Add strict versions of insertWith and insertWithKey to IntMap
Johan Tibell <johan.tibell@gmail.com>**20101030135122
 Ignore-this: 5472c9be565e75672140d243ef0211f2
] 
[Explain INLINEs in IntMap and IntSet.
Milan Straka <fox@ucw.cz>**20101104224507
 Ignore-this: 322a22056e9aa5d4e5a9f2caa6542017
] 
[Fix warnings.
Milan Straka <fox@ucw.cz>**20101104223950
 Ignore-this: 19460b7cab4554fef3b637ebb36addd1
 
 Just trivial renames of shadows variables.
] 
[Explain the nomatch clause in IntSet.hs
Milan Straka <fox@ucw.cz>**20101104221451
 Ignore-this: 2f90d0037027e77cffff30cf21729845
] 
[Rename STRICTxy to STRICT_x_OF_y.
Milan Straka <fox@ucw.cz>**20101104220917
 Ignore-this: fb12cee5518d1a8844ee44273330fa57
 
 Also explain why bang patterns are not used.
] 
[Settle performance issues in Map and Set.
Milan Straka <fox@ucw.cz>**20101031082146
 Ignore-this: 9a4c70d5f9a5884c7ff8f714ae4ff1e4
 
 Explain the INLINE/INLINABLE in the Map and Set sources.
 
 Use 'go' only for functions that can be INLINE.
] 
[Settle performance issues in IntMap and IntSet.
Milan Straka <fox@ucw.cz>**20101029231653
 Ignore-this: c1234a5113da14178a2394976e91b786
 
 The worker-wrapper transformation is removed from
 all functions but lookup and member. This is the
 only place where it causes benefits -- a 10% to
 15% speedup. It increases memory allocation
 slightly (0-5%), but the effect on GHC is really
 minor.
 
 Also INLINE/INLINABLE hints are not really needed,
 GHC figures it all by itself. The explicit INLINE
 were left on internal functions that are crutial
 to INLINE because of performance.
] 
[Make foldlStrict semantics to match foldl'.
Milan Straka <fox@ucw.cz>**20101022100939
 Ignore-this: 3790a5a47e4ff7b55c005a8c95e5890f
] 
[Remove INLINABLE in IntMap and IntSet.hs.
Milan Straka <fox@ucw.cz>**20101022091744
 Ignore-this: 4f532887bf54444989cc66d6546f1c89
 
 It makes no sense, as the calls are already specialized
 for Int keys. Benchmarks actually show small slowdown.
] 
[Do not pass f explicitely for fold.
Milan Straka <fox@ucw.cz>**20101019202043
 Ignore-this: bb0a5e758ebfebbdf8160be4317898e9
 
 Benchmarks shows this is a huge win (100% for (:) being
 the function, 1000% for (+) being the function).
] 
[Mark fold explicitely as INLINE.
Milan Straka <fox@ucw.cz>**20101016222150
 Ignore-this: b72855a0af39e57b1862908717fc14fc
 
 The INLINABLE does not work well in this case. Benchmarks
 show memory savings (due to unboxing) and nearly no GHC binary
 size increase.
] 
[Changing INLINE pragmas.
Milan Straka <fox@ucw.cz>**20101016215959
 Ignore-this: 933327354749d18e4617280fde55cce0
 
 The internal functions that need to be inlined are marked INLINE
 (bit fiddling in IntMap/IntSet, empty, singleton, bin).
 
 Aslo if INLINABLE is available, use it for all exported functions.
 The functions like insert that were INLINE because of specialization
 issues are now INLINE only in the case of INLINABLE absence.
] 
[Whitespace changes only.
Milan Straka <fox@ucw.cz>**20101016202831
 Ignore-this: 8850e09fb49937b54da6585d01aade9a
] 
[Correct a typo in macro name.
Milan Straka <fox@ucw.cz>**20101016202641
 Ignore-this: 356621b0ca954f73d543fc33d43383b2
] 
[Change the worker/wrapper to explicitly pass arguments.
Milan Straka <fox@ucw.cz>**20101016195757
 Ignore-this: 7f4a2180a263ee15cbb73c60b2d8cc46
 
 As the benchmarking showed, it is not a good idea to create
 closures in the worker/wrapper transformation, as the captured
 arguments of the enclosing function have to be allocated on the
 heap. It is better to explicitly pass the arguments on the stack.
 This saves memory and add no time penalty if the arguments are
 the first arguments of recursive function (GHC refrains from
 needless copying).
 
 The worker is often strict in some arguments. I did not want
 to use BangPatterns, so I used macros to indicate strictness.
 If majority thinks BangPatters are fine, I will gladly change it.
] 
[Fix warnings in Data.Map and Data.Set.
Milan Straka <fox@ucw.cz>**20100924154946
 Ignore-this: cb2c0a8ecf0a57acc5941ba841aa7c40
 
 Only trivial changes.
] 
[Finish the started worker/wrapper transformation.
Milan Straka <fox@ucw.cz>**20100924153353
 Ignore-this: baeb24573242beb56c3bbe7ca67f5ff7
 
 Some methods (insert, lookup) were not modified as the rest
 (like insertWith, delete, ...). Also the `seq` were missing
 sometimes.
] 
[Merge all the OPTIONS and LANGUAGE module pragmas.
Milan Straka <fox@ucw.cz>**20100924152642
 Ignore-this: 86067abf13f0501f29c13ec7c877533c
] 
[Remove most INLINE from Map, Set, IntMap and IntSet.
Milan Straka <fox@ucw.cz>**20100924152008
 Ignore-this: c88c4ede21c06bfda20af131c232a720
 
 Because of a code bloat the INLINEs cause, remove most of
 them. The only INLINEs left are the following:
 - only in Set and Map, because in IntMap and IntSet the specialization
   does not help
 - only on functions which need Ord
 - only on 'small' functions, namely member, notMember, lookup*,
   insert*, delete*, adjust*, alter*, update*
 
 All other functions of Map, Set, IntMap and IntSet are marked INLINABLE,
 even if they are recursive.
 
 The INLINEs left are only a short-term solution. In the long run the
 auto-specialization of INLINABLE methods seems a good way (maybe
 SPECIALIZABLE).
] 
[Comment tests and benchmarks on foldlWithKey' which
Milan Straka <fox@ucw.cz>**20100924110705
 Ignore-this: 71b988389e6ae9a78ea3b0e20156ca2f
 was commented recently by Ian Lynagh.
] 
[Worker/wrapper transformation for Data.IntSet.
Milan Straka <fox@ucw.cz>**20100923125604
 Ignore-this: b0228582818f7bfb690d0853022a7809
] 
[Compile only the benchmark source, not the Data/*.hs.
Milan Straka <fox@ucw.cz>**20100921115821
 Ignore-this: f94d9e3ffe126cd057d23490c973a4e9
] 
[Add criterion-based benchmark for IntSet.hs.
Milan Straka <fox@ucw.cz>**20100921103225
 Ignore-this: 3d31a820830c7382748626bc9a1ba54
 
 The benchmark is nearly identical copy of Set.hs benchmark.
] 
[Add a testsuite for Data.IntSet.
Milan Straka <fox@ucw.cz>**20100921102802
 Ignore-this: e55484ee185e71915452bdf2a7b2a2b3
] 
[Further improve Data.Set balance function.
Milan Straka <fox@ucw.cz>**20100921091828
 Ignore-this: f23be37859224e9bbe919a3c0a71fdc6
 
 As suggested by Kazu Yamamoto, we split balance to balanceL and
 balanceR, which handle only one-sided inbalance, but need fewer
 tests than balance.
 
 As nearly all functions modifying the structure use balance, this
 results in speedup of many functions. On my 32-bit GHC 6.12.1,
 11% speedup for insert, 12% speedup for delete.
] 
[Further improve Data.Map balance function.
Milan Straka <fox@ucw.cz>**20100921091547
 Ignore-this: 8abfd027142a5183b2b5282e96ccb414
 
 As suggested by Kazu Yamamoto, we split balance to balanceL and
 balanceR, which handle only one-sided inbalance, but need fewer
 tests than balance.
 
 As nearly all functions modifying the structure use balance, this
 results in speedup of many functions. On my 32-bit GHC 6.12.1,
 20% speedup for insert, 7% speedup for delete, 5% speedup for update.
] 
[Changing delta to 3 in Data.Set.
Milan Straka <fox@ucw.cz>**20100921090507
 Ignore-this: a47d0c542ed9cee99ad6b17c52c977a1
 
 Only possible values are 3 and 4. The value 3 has much faster inserts,
 value 4 slightly faster deletes, so choosing 3.
 
 Also changed the inequalities to rebalance only when one subtree
 is _strictly_ larger than delta * the other one, to mimic the behaviour
 from the proof (both from the Adams' and from the one to come).
] 
[Changing delta to 3 in Data.Map.
Milan Straka <fox@ucw.cz>**20100921090358
 Ignore-this: 85f733f836b65b2b1038383ddb92e8e1
 
 Only possible values are 3 and 4. The value 3 has much faster inserts,
 value 4 slightly faster deletes, so choosing 3.
 
 Also changed the inequalities to rebalance only when one subtree
 is _strictly_ larger than delta * the other one, to mimic the behaviour
 from the proof (both from the Adams' and from the one to come).
] 
[Correct Data.Set Arbitrary instance never to return unbalanced trees.
Milan Straka <fox@ucw.cz>**20100914150442
 Ignore-this: b5c70fa98a56f225b8eb5faf420677b0
 
 The previous instance sometimes returned unbalanced trees,
 which broke the tests.
 
 Also the new instance mimics Data.Map instance more closely in the shape
 of the generated trees.
] 
[Correct Data.Map Arbitrary instance never to return unbalanced trees.
Milan Straka <fox@ucw.cz>**20100914145841
 Ignore-this: 114bbcc63acdb16b77140ea56aeb0a95
 
 The previous instance sometimes returned unbalanced trees,
 which broke the tests.
] 
[Improve Data.Set benchmark.
Milan Straka <fox@ucw.cz>**20100914142010
 Ignore-this: 9b878ae3aa5a43ef083abfd7f9b22513
 
 Add union, difference and intersection to Data.Set benchmark.
] 
[Improve benchmark infrastructure and Data.Map benchmark.
Milan Straka <fox@ucw.cz>**20100914141707
 Ignore-this: 67e8dafcb4abcb9c726b9b29c7c320fd
 
 Renamed Benchmarks.hs to Map.hs, as it only benchmarks Data.Map.
 Improve the Makefile to work with multiple benchmarks.
 Add union, difference and intersection to Data.Map benchmark.
] 
[Improve the performance of Data.Set balance function.
Milan Straka <fox@ucw.cz>**20100914140417
 Ignore-this: 577c511c219695b8d483af546c7387e8
 
 The balance function is now one monolithic function, which allows
 to perform all pattern-matches only once.
 
 Nearly all functions modifying Data.Map use balance.
 The improvements are 12% for insert, 14% for delete (GHC 6.12.1).
] 
[Improve the performance of Data.Map balance function.
Milan Straka <fox@ucw.cz>**20100914140217
 Ignore-this: 951181e035fcac90674dff3300350a1
 
 The balance function is now one monolithic function, which allows
 to perform all pattern-matches only once.
 
 Nearly all functions modifying Data.Map use balance.
 The improvements are 7-11% for various insert*, delete*, alter,
 update or intersection functions (GHC 6.12.1).
] 
[Improve performance of Data.Set union and difference operations.
Milan Straka <fox@ucw.cz>**20100914135725
 Ignore-this: 6dc4a186ea060b9cdb9e783db71ca280
 
 Use datatype storing evaluated bound instead of high-order functions.
 The improvements are over 25% for both union and difference (GHC 6.12.1).
] 
[Improve performance of Data.Map union* and difference* operations.
Milan Straka <fox@ucw.cz>**20100914134614
 Ignore-this: 35b23a40ef33e9fa14eb81fdee4b152d
 
 Use datatype storing evaluated bound instead of high-order functions.
 The improvements are 22% for union and 20% for difference (GHC 6.12.1).
] 
[Make the Set store the elements evaluated (bang added).
Milan Straka <fox@ucw.cz>**20100913165132
 Ignore-this: b3f230db5bf30d93d3fddf2c81c5f3b4
] 
[Improved performance of Data.Set
Johan Tibell <johan.tibell@gmail.com>**20100831124352
 Ignore-this: 38a304a0408d29a2956aa9a1fc0ce755
 
 Performance improvements are due to manually applying the
 worker/wrapper transformation and strictifying the keys.
 
 Average speed-up is 32% on a 2GHz Core 2 Duo on OS X 10.5.8
] 
[Added benchmarks for Data.Set
Johan Tibell <johan.tibell@gmail.com>**20100831124225
 Ignore-this: fcacf88761034b8c534d936f0b336cc0
] 
[Added a test suite for Data.Set
Johan Tibell <johan.tibell@gmail.com>**20100831124030
 Ignore-this: f430dc302c0fcb8b5d62db2272a1d6f7
 
 Expression coverage: 74%
] 
[Remove use of lambdas with irrefutable patterns
simonpj@microsoft.com**20100923120838
 Ignore-this: c36e90a0258c0d5262684c585c321419
] 
[Revert the recent contentious changes
Ian Lynagh <igloo@earth.li>**20100915135103
 Ignore-this: fe4f71ff1ade51c11421dc9974aa0fda
 These will probably be tidied up and reinstated later, but this gets
 the package back to a releasable state.
] 
[fix warnings
Simon Marlow <marlowsd@gmail.com>**20100831114555
 Ignore-this: 53df71bc054a779b8ad2dad89c09e02d
] 
[Missing MagicHash for IntSet
Don Stewart <dons@galois.com>**20100831093446
 Ignore-this: d075f760adb9a2aa0ee04676e38a07cc
] 
[Performance improvements for Data.IntMap (worker/wrapper and inlining)
Don Stewart <dons@galois.com>**20100831093316
 Ignore-this: 206036448558d270f0eb85ef4cd55368
] 
[Add criterion-based benchmarking for IntMap
Don Stewart <dons@galois.com>**20100831093240
 Ignore-this: d7d85b9afb513532cc30f5b51a3f825e
] 
[Add comprehensive testsuite for IntMap
Don Stewart <dons@galois.com>**20100831093202
 Ignore-this: d455fedbc615e5b63ac488e605550557
] 
[-O2 -fregs-graph is a uniform 10% improvements for IntMap
Don Stewart <dons@galois.com>**20100831092956
 Ignore-this: 2372cf4be945fe7939d0af94e32c567f
] 
[Missed base case for updateAt worker. Spotted by Jan-Willem Maessen
Don Stewart <dons@galois.com>**20100829163329
 Ignore-this: b8daf1c55c163c16f50c3b54cca2dba1
] 
[Major bump (new functions, clarified strictness properties, vastly better performance)
Don Stewart <dons@galois.com>**20100829122628
 Ignore-this: 9bfbc58ecaa24a86be37b8c4cb043457
] 
[Add two new functions: foldlWithKey' and insertLookupWithKey'
Don Stewart <dons@galois.com>**20100829122147
 Ignore-this: a2f112653ba38737fe1b38609e06c314
 
 These two functions use strict accumulators, compared to their existing
 counterparts (which are lazy left folds, that appear not to be useful). 
 Performance is significantly better.
 
] 
[Performance improvements to Data.Map
Don Stewart <dons@galois.com>**20100829120245
 Ignore-this: b4830cddfa6d62e4883f4e0f58ac4e57
 
 Applied several standard transformations to improve the performance of
 code:
 
     * Worker/wrapper of all recursive functions with constant arguments
     * Inlining of all (non-recursive) wrappers
     * Consistent use of strict keys
 
 Average performance improvements across common API (with GHC 6.12.3):
 
     * Linux / x86_64 / 2.6Ghz i7        : 48%
     * Mac OSX 10.5 / x86 / 2 Ghz Xeon   : 36%
 
 Graphs and raw data: http://is.gd/eJHIE
 
 This patch is (mostly) orthogonal to the algorithmic changes suggested
 by Milan Straka in his HW 2010 paper:
 
     http://research.microsoft.com/~simonpj/papers/containers/containers.pdf
 
 Those changes could be added separately, for some additional improvments.
 
 Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell
 and Don Stewart.
 
] 
[Add a criterion-based benchmark suite for Data.Map
Don Stewart <dons@galois.com>**20100829114611
 Ignore-this: ec61668f5bcb78bd15b72e2728c01c19
 
 This adds a criterion-based micro-benchmarking suite for Data.Map. It
 can be used to measure performance improvements for individual top-level
 functions.
 
 Examples here: http://is.gd/eJHIE
 
] 
[Add a comprehensive testsuite for Data.Map
Don Stewart <dons@galois.com>**20100829113545
 Ignore-this: 891e7fe6bac3523868714ac1ff51c0a3
 
 This patch adds a joint quickcheck2 / hunit testsuite, with coverage of
 91% of top level functions (remaining features are mostly in instances).
 
 The coverage data is here: 
     
     http://code.haskell.org/~dons/tests/containers/hpc_index.html
 
 No bugs were found. It includes unit tests for known past bugs
 (balancing).
 
] 
[Oops, get the #ifdef symbol correct.
Malcolm.Wallace@me.com**20100902081938] 
[Protect a gratuitous GHC-ism with #ifdefs.
Malcolm.Wallace@me.com**20100902081217] 
[Set Data.Map's delta to 4; fixes #4242
Ian Lynagh <igloo@earth.li>**20100815131954] 
[Add a test for #4242
Ian Lynagh <igloo@earth.li>**20100815131856] 
[Add a local type signature
simonpj@microsoft.com**20100730124447
 Ignore-this: b581d3f2c80a7a860456d589960f12f2
] 
[Add type signature in local where clause
simonpj@microsoft.com**20100727151709
 Ignore-this: 5929c4156500b25b280eb414b508c508
] 
[Fix Data.Sequence's breakr, and add a test for it; fixes trac #4157
Ian Lynagh <igloo@earth.li>**20100704140627] 
[Fix proposal #4109: Make Data.Map.insertWith's strictness consistent
Ian Lynagh <igloo@earth.li>**20100615133055] 
[Tweak layout to work with the alternative layout rule
Ian Lynagh <igloo@earth.li>**20091129154519] 
[Disable building Data.Sequence (and dependents) for nhc98.
Malcolm.Wallace@cs.york.ac.uk**20091124025653
 There is some subtlety of polymorphically recursive datatypes and
 type-class defaulting that nhc98's type system barfs over.
] 
[Fix another instance of non-ghc breakage.
Malcolm.Wallace@cs.york.ac.uk**20091123092637] 
[Add #ifdef around ghc-only (<$) as member of Functor class.
Malcolm.Wallace@cs.york.ac.uk**20091123085155] 
[Fix broken code in non-GHC branch of an ifdef.
Malcolm.Wallace@cs.york.ac.uk**20091123084824] 
[doc bugfix: correct description of index argument
Ross Paterson <ross@soi.city.ac.uk>**20091028105532
 Ignore-this: 9790e7bf422c4cb528722c03cfa4fed9
 
 As noted by iaefai on the libraries list.
 
 Please merge to STABLE.
] 
[Bump version to 0.3.0.0
Ian Lynagh <igloo@earth.li>**20090920141847] 
[update base dependency
Ross Paterson <ross@soi.city.ac.uk>**20090916073125
 Ignore-this: ad382ffc6c6a18c15364e6c072f19edb
 
 The package uses mkNoRepType and Data.Functor, which were not in the
 stable branch of base-4.
] 
[add fast version of <$ for Seq
Ross Paterson <ross@soi.city.ac.uk>**20090916072812
 Ignore-this: 5a39a7d31d39760ed589790b1118d240
] 
[new methods for Data.Sequence (proposal #3271)
Ross Paterson <ross@soi.city.ac.uk>**20090915173324
 Ignore-this: cf17bedd709a6ab3448fd718dcdf62e7
 
 Adds a lot of new methods to Data.Sequence, mostly paralleling those
 in Data.List.  Several of these are significantly faster than versions
 implemented with the previous public interface.  In particular, replicate
 takes O(log n) time and space instead of O(n).
 (by Louis Wasserman)
] 
[Fix "Cabal check" warnings
Ian Lynagh <igloo@earth.li>**20090811215900] 
[TAG 2009-06-25
Ian Lynagh <igloo@earth.li>**20090625160202] 
Patch bundle hash:
90e1dd96277f1fdd8621bb2b2fd56ad0ea89f9ce