Define reducing operations in Data.Foldable in terms of foldl' instead of foldMap or foldl1

Summary

This is a performance issue for the base library. The following operations in Data.Foldable take O(n) amount of space and non-optimal amount of time, which makes them of little use in practice. They can lead to performance issues that makes people waste a lot of time in debugging.

Type class operations:

• minimum
• maximum
• sum
• product

Non type class operations:

• minimumBy
• maximumBy

Also, not having an INLINABLE or INLINE on these and other operations in Data.Foldable makes global optimization involving these operations impossible and therefore requires re-definition to achieve that.

Steps to reproduce

Run the benchmarks at this commit (https://github.com/composewell/streamly/tree/b50e1a52850f8fdd1e70797815047cc7333f743d) in the streamly repository using the following command:

cabal run linear -- serially/foldable

If you increase the size of the stream, the amount of memory required would increase linearly, the following command demonstrates that:

cabal run linear -- --stream-size 100000000 serially/foldable

Expected behavior

It should run in constant memory and with much better timings for these operations. When these operations are implemented using foldl' we can see the difference in performance by running the above commands on this commit https://github.com/composewell/streamly/tree/007df998b99bcbea168763fccd79d49164ab04c9 .

The comparison of benchmarks can be seen in this pull request - https://github.com/composewell/streamly/pull/416 . In this PR we could fix the performance of those operations which are part of the Foldable type class, but we cannot fix minimumBy and maximumBy because they are not in the type class. However, they can also be fixed generically if we use foldl' instead of foldl1.

Our definitions of the type class operations can be found here: https://github.com/composewell/streamly/blob/04f84d34598b8d3f125b4919f51afb4b233f281e/src/Streamly/Internal/Data/Stream/Instances.hs#L138

Related Issues

Similar issues seem to have been discussed in ghc ticket #10830 (closed) specifically in this comment https://gitlab.haskell.org//ghc/ghc/issues/10830#note_129843.

Is there a good reason to use foldMap, foldl1 for these operations instead of using foldl'?

I understand that some of these operations can terminate early in some cases e.g. product can terminate if it becomes 0. However, those cases cannot be used as an excuse to penalize all other cases heavily. I think, in practice, it makes better sense to implement these using a strict left fold by default and if early termination cases are important to someone they can use custom definitions.

At the very least, the foldl1 in maximumBy and minimumBy can be replaced with foldl'.

Environment

• GHC version used: 8.8.2

Optional:

• Operating System: Mac OS
• System Architecture: x86_64