Announcing containers 0.5.8.1
There's a lot to see in this one. There are plenty of brand-new functions in Data.Map, Data.Set, and Data.Sequence, including a highly-optimized lens-inspired map alteration function and a brand-new API for merging maps efficiently. Several key map, set, and sequence functions have sped up considerably. The full change log is below. I have tried to give appropriate credit to all the non-maintainers who contributed to this release, some of whom made very major contributions indeed. If I missed anyone, please give a shout. General package changes: Remove all attempts to support nhc98 and any versions of GHC before 7.0. Integrate benchmarks with Cabal. (Thanks, Gabriel Gonzalez!) Make Cabal report required extensions properly, and stop using default extensions. Note that we do not report extensions conditionally enabled based on GHC version, as doing so would lead to a maintenance nightmare with no obvious benefits. Use BangPatterns throughout to reduce noise. This extension is now required to compile containers. Improve QuickCheck properties taking arbitrary functions by using Test.QuickCheck.Function.Fun instead of evil Show instances for functions. Expose several internal modules through Cabal (as requested by Edward Kmett). These remain completely unsupported. New exports and instances: Add alterF, restrictKeys, and withoutKeys to Data.Map and Data.IntMap. Add take, drop, splitAt, takeWhileAntitone, dropWhileAntitone, and spanAntitone for Data.Map and Data.Set. Thanks to Cale Gibbard for suggesting these. Add merge, mergeA, and associated merge tactics for Data.Map. Many thanks to Cale Gibbard, Ryan Trinkle, and Dan Doel for inspiring the merge idea and helping refine the interface. Add fromDescList, fromDescListWith, fromDescListWithKey, and fromDistinctDescList to Data.Map. Add fromDescList and fromDistinctDescList to Data.Set. Add Empty, :<|, and :|> pattern synonyms for Data.Sequence, as originally envisioned in the finger tree paper by Paterson and Hinze. Add adjust', (!?), lookup, chunksOf, cycleTaking, insertAt, deleteAt, intersperse, foldMapWithIndex, and traverseWithIndex for Data.Sequence. Derive Generic and Generic1 for Data.Tree.Tree, Data.Sequence.ViewL, and Data.Sequence.ViewR. Add foldTree for Data.Tree. (Thanks, Daniel Wagner!) Semantic changes: Make Data.Sequence.splitAt strict in its arguments. Previously, it returned a lazy pair. Fix completely erroneous definition of length for Data.Sequence.ViewR. Make Data.Map.Strict.traverseWithKey force result values before installing them in the new map. Make Data.Tree.drawTree handle newlines better. (Thanks, recursion-ninja!) Deprecations: All functions in Data.Map proper that have been documented as deprecated since version 0.5 or before now have DEPRECATED pragmas and will actually be removed after another cycle or two. Tree printing functions in Data.Map intended for library debugging are now deprecated. They will continue to be available for the foreseeable future in an internal module. Performance changes: Substantially speed up splitAt, zipWith, take, drop, fromList, partition, foldl', and foldr' for Data.Sequence. Special thanks to Lennart Spitzner for digging into the performance problems with previous versions of fromList and finding a way to make it really fast. Slightly optimize replicateA. Stop traverse from performing many unnecessary fmap operations. Most operations in Data.Sequence advertised as taking logarithmic time (including >< and adjust) now use their full allotted time to avoid potentially building up chains of thunks in the tree. In general, the only remaining operations that avoid doing more than they really need are the particular bulk creation and transformation functions that really benefit from the extra laziness. There are some situations where this change may slow programs down, but I think having more predictable and usually better performance more than makes up for that. Add rewrite rules to fuse fmap with reverse for Data.Sequence. Switch from hedge algorithms to divide-and-conquer algorithms for union, intersection, difference, and merge in both Data.Map and Data.Set. These algorithms are simpler, are known to be asymptotically optimal, and are faster according to our benchmarks. Speed up adjust for Data.Map. Allow map to inline, and define a custom (<$). This considerably improves mapping with a constant function. Remove non-essential laziness throughout the Data.Map.Lazy implementation. Slightly speed up deletion and alteration functions for Data.IntMap.
Wow, thanks!
ср, 31 авг. 2016 г. в 10:52, David Feuer
There's a lot to see in this one. There are plenty of brand-new functions in Data.Map, Data.Set, and Data.Sequence, including a highly-optimized lens-inspired map alteration function and a brand-new API for merging maps efficiently. Several key map, set, and sequence functions have sped up considerably. The full change log is below. I have tried to give appropriate credit to all the non-maintainers who contributed to this release, some of whom made very major contributions indeed. If I missed anyone, please give a shout.
General package changes:
Remove all attempts to support nhc98 and any versions of GHC before 7.0.
Integrate benchmarks with Cabal. (Thanks, Gabriel Gonzalez!)
Make Cabal report required extensions properly, and stop using default extensions. Note that we do not report extensions conditionally enabled based on GHC version, as doing so would lead to a maintenance nightmare with no obvious benefits.
Use BangPatterns throughout to reduce noise. This extension is now required to compile containers.
Improve QuickCheck properties taking arbitrary functions by using Test.QuickCheck.Function.Fun instead of evil Show instances for functions.
Expose several internal modules through Cabal (as requested by Edward Kmett). These remain completely unsupported.
New exports and instances:
Add alterF, restrictKeys, and withoutKeys to Data.Map and Data.IntMap.
Add take, drop, splitAt, takeWhileAntitone, dropWhileAntitone, and spanAntitone for Data.Map and Data.Set. Thanks to Cale Gibbard for suggesting these.
Add merge, mergeA, and associated merge tactics for Data.Map. Many thanks to Cale Gibbard, Ryan Trinkle, and Dan Doel for inspiring the merge idea and helping refine the interface.
Add fromDescList, fromDescListWith, fromDescListWithKey, and fromDistinctDescList to Data.Map.
Add fromDescList and fromDistinctDescList to Data.Set.
Add Empty, :<|, and :|> pattern synonyms for Data.Sequence, as originally envisioned in the finger tree paper by Paterson and Hinze.
Add adjust', (!?), lookup, chunksOf, cycleTaking, insertAt, deleteAt, intersperse, foldMapWithIndex, and traverseWithIndex for Data.Sequence.
Derive Generic and Generic1 for Data.Tree.Tree, Data.Sequence.ViewL, and Data.Sequence.ViewR.
Add foldTree for Data.Tree. (Thanks, Daniel Wagner!)
Semantic changes:
Make Data.Sequence.splitAt strict in its arguments. Previously, it returned a lazy pair.
Fix completely erroneous definition of length for Data.Sequence.ViewR.
Make Data.Map.Strict.traverseWithKey force result values before installing them in the new map.
Make Data.Tree.drawTree handle newlines better. (Thanks, recursion-ninja!)
Deprecations:
All functions in Data.Map proper that have been documented as deprecated since version 0.5 or before now have DEPRECATED pragmas and will actually be removed after another cycle or two.
Tree printing functions in Data.Map intended for library debugging are now deprecated. They will continue to be available for the foreseeable future in an internal module.
Performance changes:
Substantially speed up splitAt, zipWith, take, drop, fromList, partition, foldl', and foldr' for Data.Sequence. Special thanks to Lennart Spitzner for digging into the performance problems with previous versions of fromList and finding a way to make it really fast. Slightly optimize replicateA. Stop traverse from performing many unnecessary fmap operations.
Most operations in Data.Sequence advertised as taking logarithmic time (including >< and adjust) now use their full allotted time to avoid potentially building up chains of thunks in the tree. In general, the only remaining operations that avoid doing more than they really need are the particular bulk creation and transformation functions that really benefit from the extra laziness. There are some situations where this change may slow programs down, but I think having more predictable and usually better performance more than makes up for that.
Add rewrite rules to fuse fmap with reverse for Data.Sequence.
Switch from hedge algorithms to divide-and-conquer algorithms for union, intersection, difference, and merge in both Data.Map and Data.Set. These algorithms are simpler, are known to be asymptotically optimal, and are faster according to our benchmarks.
Speed up adjust for Data.Map. Allow map to inline, and define a custom (<$). This considerably improves mapping with a constant function.
Remove non-essential laziness throughout the Data.Map.Lazy implementation.
Slightly speed up deletion and alteration functions for Data.IntMap. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
On Wed, 31 Aug 2016, David Feuer wrote:
Use BangPatterns throughout to reduce noise. This extension is now required to compile containers.
Btw. there is no strong need for BangPatterns. Instead of f !x !y = ... you can write f = strict2 $ \x y -> ... {-# INLINE strict2 #-} strict2 :: (a -> b -> x) -> a -> b -> x strict2 f a b = (f $! a) $! b Sometimes I hope that availability of portable libraries would help non-mainstream compilers to gain ground.
Wren and I made the decision to use bang patterns to make it easier for us
to read and write the code. We hope that rather modest extension will be in
the next Haskell Report. From my perspective, this decision is
non-negotiable. It's just too hard for my poor brain to work with all the
possible strictification functions we'd need for various numbers of
arguments and the awkwardness required to use them. This was previously
done with a combination of manual seq and CPP, and I found it nasty.
On Aug 31, 2016 5:10 AM, "Henning Thielemann"
On Wed, 31 Aug 2016, David Feuer wrote:
Use BangPatterns throughout to reduce noise. This extension is now
required to compile containers.
Btw. there is no strong need for BangPatterns. Instead of
f !x !y = ...
you can write
f = strict2 $ \x y -> ...
{-# INLINE strict2 #-} strict2 :: (a -> b -> x) -> a -> b -> x strict2 f a b = (f $! a) $! b
Sometimes I hope that availability of portable libraries would help non-mainstream compilers to gain ground.
On 31 August 2016 at 12:10, Henning Thielemann
On Wed, 31 Aug 2016, David Feuer wrote:
Use BangPatterns throughout to reduce noise. This extension is now required to compile containers.
Btw. there is no strong need for BangPatterns. Instead of
...
Sometimes I hope that availability of portable libraries would help non-mainstream compilers to gain ground.
Compiler that doesn't support bang patterns (and half of GHC extensions) cannot gain ground.
On Wed, Aug 31, 2016 at 6:44 AM, Alexey Khudyakov
On 31 August 2016 at 12:10, Henning Thielemann wrote:
Sometimes I hope that availability of portable libraries would help non-mainstream compilers to gain ground.
Compiler that doesn't support bang patterns (and half of GHC extensions) cannot gain ground.
Bang patterns (i.e., the kind we are using which are always top-level, not intermixed with patterns) are an extremely simple extension. Every time someone says "it's so easy to avoid BangPatterns, you can just..."— well, yes: it's so easy, alternative compilers can do exactly what you suggest in order to implement BangPatterns. The whole point of BangPatterns is not to increase expressivity of Haskell, it's to clean up code by saying what you mean. In Haskell we value saying what we mean, and avoiding exposing implementation-detail cruftiness; and this is simply another example of that. By avoiding CPP hackery we (a) make the containers code much cleaner and easier to read, (b) avoid needing to worry about CPP possibly doing unexpected things, and (c) avoid needing to worry about whether our tests actually test what we mean (since using CPP means doing variational programming, so we don't necessarily run the variant of the code we think we are). -- Live well, ~wren
participants (5)
-
Alexey Khudyakov -
David Feuer -
Geraldus -
Henning Thielemann -
wren romano