List-monomorphic `foldr'`

While a *strict* (i.e. constant space) right-fold on lists is not
possible, the default `foldr'` is optimised for structures like
`Seq`, that support efficient access to the right-most elements.
The original default implementation seems to have a better
constant factor for lists, so we add a monomorphic implementation
in GHC.List.

Should this be re-exported from `Data.List`?  That would be a
user-visible change if both `Data.Foldable` and `Data.List` are
imported unqualified...

2 files changed, 44 insertions, 10 deletions

diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs
index c9e48bb868..5137aa76d7 100644
--- a/libraries/base/Data/Foldable.hs
+++ b/libraries/base/Data/Foldable.hs
@@ -723,9 +723,10 @@ instance Foldable [] where
     foldl'  = List.foldl'
     foldl1  = List.foldl1
     foldr   = List.foldr
+    foldr'  = List.foldr'
+    foldr1  = List.foldr1
     foldMap = (mconcat .) . map -- See Note [Monoidal list folds]
     fold    = mconcat           -- See Note [Monoidal list folds]
-    foldr1  = List.foldr1
     length  = List.length
     maximum = List.maximum
     minimum = List.minimum
diff --git a/libraries/base/GHC/List.hs b/libraries/base/GHC/List.hs
index 1348d5215f..3408538568 100644
--- a/libraries/base/GHC/List.hs
+++ b/libraries/base/GHC/List.hs
@@ -20,14 +20,19 @@
 module GHC.List (
    -- [] (..),          -- built-in syntax; can't be used in export list
 
-   map, (++), filter, concat,
-   head, last, tail, init, uncons, null, length, (!!),
-   foldl, foldl', foldl1, foldl1', scanl, scanl1, scanl', foldr, foldr1,
-   scanr, scanr1, iterate, iterate', repeat, replicate, cycle,
-   take, drop, sum, product, maximum, minimum, splitAt, takeWhile, dropWhile,
-   span, break, reverse, and, or,
-   any, all, elem, notElem, lookup,
-   concatMap,
+   -- List-monomorphic Foldable methods and misc functions
+   foldr, foldr', foldr1,
+   foldl, foldl', foldl1,
+   null, length, elem, notElem,
+   maximum, minimum, sum, product, and, or, any, all,
+
+   -- Other functions
+   foldl1', concat, concatMap,
+   map, (++), filter, lookup,
+   head, last, tail, init, uncons, (!!),
+   scanl, scanl1, scanl', scanr, scanr1,
+   iterate, iterate', repeat, replicate, cycle,
+   take, drop, splitAt, takeWhile, dropWhile, span, break, reverse,
    zip, zip3, zipWith, zipWith3, unzip, unzip3,
    errorEmptyList,
 
@@ -550,9 +555,37 @@ Based on nofib benchmarks, this is bad for performance. Therefore, we instead
 match on everything past the :, which is just the tail of scanl.
 -}
 
--- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
+-- foldr, foldr', foldr1, scanr, and scanr1 are the right-to-left duals of the
 -- above functions.
 
+-- | 'foldr'' is a variant of 'foldr' that begins list reduction from the last
+-- element and evaluates the accumulator strictly as it unwinds the stack back
+-- to the beginning of the list.  The input list /must/ be finite, otherwise
+-- 'foldr'' runs out of space (/diverges/).
+--
+-- Note that if the function that combines the accumulated value with each
+-- element is strict in the accumulator, other than a possible improvement
+-- in the constant factor, you get the same \(\mathcal{O}(n)\) space cost
+-- as with just 'foldr'.
+--
+-- If you want a strict right fold in constant space, you need a structure
+-- that supports faster than \(\mathcal{O}(n)\) access to the right-most
+-- element, such as @Seq@ from the @containers@ package.
+--
+-- Use of this function is a hint that the @[]@ structure may be a poor fit
+-- for the task at hand.  If the order in which the elements are combined is
+-- not important, use 'foldl'' instead.
+--
+-- >>> foldr' (+) [1..4]  -- Use foldl' instead!
+-- 10
+-- >>> foldr' (&&) [True, False, True, True] -- Use foldr instead!
+-- False
+-- >>> foldr' (||) [False, False, True, True] -- Use foldr instead!
+-- True
+foldr' :: (a -> b -> b) -> b -> [a] -> b
+foldr' f z0 xs = foldl f' id xs z0
+  where f' k x z = k $! f x z
+
 -- | 'foldr1' is a variant of 'foldr' that has no starting value argument,
 -- and thus must be applied to non-empty lists. Note that unlike 'foldr', the accumulated value must be of the same type as the list elements.
 --