Fixes a spaceleak in `maximumBy` and `minimumBy` (#10830).
authorRyan Scott <ryan.gl.scott@gmail.com>
Fri, 3 Mar 2017 22:49:35 +0000 (17:49 -0500)
committerBen Gamari <ben@smart-cactus.org>
Sat, 4 Mar 2017 21:04:14 +0000 (16:04 -0500)
This involved changing the implementation from using
`foldr11` to using `foldl1`.

Test Plan: validate

Reviewers: austin, hvr, bgamari, dalaing, dfeuer

Reviewed By: bgamari

Subscribers: RyanGlScott, dfeuer, thomie

Differential Revision: https://phabricator.haskell.org/D3019

libraries/base/Data/Foldable.hs
libraries/base/changelog.md

index 0a8b003..1d9fc92 100644 (file)
@@ -551,16 +551,20 @@ all p = getAll #. foldMap (All #. p)
 
 -- | The largest element of a non-empty structure with respect to the
 -- given comparison function.
+
+-- See Note [maximumBy/minimumBy space usage]
 maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
-maximumBy cmp = foldr1 max'
+maximumBy cmp = foldl1 max'
   where max' x y = case cmp x y of
                         GT -> x
                         _  -> y
 
 -- | The least element of a non-empty structure with respect to the
 -- given comparison function.
+
+-- See Note [maximumBy/minimumBy space usage]
 minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
-minimumBy cmp = foldr1 min'
+minimumBy cmp = foldl1 min'
   where min' x y = case cmp x y of
                         GT -> y
                         _  -> x
@@ -574,3 +578,25 @@ notElem x = not . elem x
 -- 'Nothing' if there is no such element.
 find :: Foldable t => (a -> Bool) -> t a -> Maybe a
 find p = getFirst . foldMap (\ x -> First (if p x then Just x else Nothing))
+
+{-
+Note [maximumBy/minimumBy space usage]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+When the type signatures of maximumBy and minimumBy were generalized to work
+over any Foldable instance (instead of just lists), they were defined using
+foldr1. This was problematic for space usage, as the semantics of maximumBy
+and minimumBy essentially require that they examine every element of the
+data structure. Using foldr1 to examine every element results in space usage
+proportional to the size of the data structure. For the common case of lists,
+this could be particularly bad (see Trac #10830).
+
+For the common case of lists, switching the implementations of maximumBy and
+minimumBy to foldl1 solves the issue, as GHC's strictness analysis can then
+make these functions only use O(1) stack space. It is perhaps not the optimal
+way to fix this problem, as there are other conceivable data structures
+(besides lists) which might benefit from specialized implementations for
+maximumBy and minimumBy (see
+https://ghc.haskell.org/trac/ghc/ticket/10830#comment:26 for a further
+discussion). But using foldl1 is at least always better than using foldr1, so
+GHC has chosen to adopt that approach for now.
+-}
index 3bb60fe..f39e149 100644 (file)
     functions which solely match again `ErrorCall` do not produce
     non-exhaustive pattern-match warnings (#8779)
 
+  * Change the implementations of `maximumBy` and `minimumBy` from
+    `Data.Foldable` to use `fold11` instead of `foldr1`. This makes them run
+    in constant space when applied to lists. (#10830)
+
 ## 4.9.0.0  *May 2016*
 
   * Bundled with GHC 8.0