Address review feedback on chirality

Also added nested foldr example for `concat`.

1 files changed, 45 insertions, 11 deletions

diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs
index 8e797f33f2..94bfa096a1 100644
--- a/libraries/base/Data/Foldable.hs
+++ b/libraries/base/Data/Foldable.hs
@@ -1567,11 +1567,12 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context.
 --
 -- #chirality#
 -- Foldable structures are generally expected to be efficiently iterable from
--- left to right. Right-to-left iteration may be substantially more costly,
--- or even impossible (as with, for example, infinite lists).  The text in
--- the sections below that describes performance differences between
--- left-associative right-associative folds pessimistically assumes such
--- /left-handed/ structures.
+-- left to right. Right-to-left iteration may be substantially more costly, or
+-- even impossible (as with, for example, infinite lists).  The text in the
+-- sections that follow that suggests performance differences between
+-- left-associative and right-associative folds assumes /left-handed/
+-- structures in which left-to-right iteration is cheaper than right-to-left
+-- iteration.
 --
 -- In finite structures for which right-to-left sequencing no less efficient
 -- than left-to-right sequencing, there is no inherent performance distinction
@@ -1593,12 +1594,31 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context.
 -- folds as 'foldr'.
 --
 -- Finally, in some less common structures (e.g. /snoc/ lists) right to left
--- iterations are cheaper than left to right.  For these, you may need to flip
--- left and right in the descriptions below.  When using such a structure, you
--- may also need to pay careful attention to the chirality of the fold's
--- /operator/ function, it may need to be flipped when its strictness is
--- different between its first and second argument (it will of course need to
--- be flipped when its argument types are different).
+-- iterations are cheaper than left to right.  Such structures are poor
+-- candidates for a @Foldable@ instance, and are perhaps best handled via their
+-- type-specific interfaces.  If nevertheless a @Foldable@ instance is
+-- provided, the material in the sections that follow applies to these also, by
+-- replacing each method with one with the opposite associativity (when
+-- available) and switching the order of arguments in the /operator/ function.
+--
+-- You may need to pay careful attention to strictness of the fold's /operator/
+-- when its strictness is different between its first and second argument.
+-- For example, while @('+')@ is expected to be commutative and strict in both
+-- arguments, the list concatenation operator @('++')@ is not commutative and
+-- is only strict in the initial constructor of its first argument.  The fold:
+--
+-- > myconcat xs = foldr (\a b -> a ++ b) [] xs
+--
+-- is subtantially cheaper (linear in the length of the consumed portion of the
+-- final list, thus e.g. constant time/space for just the first element) than:
+--
+-- > revconcat xs = foldr (\a b -> b ++ a) [] xs
+--
+-- In which the total cost scales up with both the number of lists combined and
+-- the number of elements ultimately consumed.  A more efficient way to combine
+-- lists in reverse order, is to use:
+--
+-- > revconcat = foldr (++) [] . reverse
 
 --------------
 
@@ -1731,6 +1751,20 @@ https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context.
 -- container types.
 --
 -- > toList = foldr (:) []
+--
+-- A more complex example is concatenation of a list of lists expressed as a
+-- nested right fold (bypassing @('++')@).  We can check that the definition is
+-- indeed lazy by folding an infinite list of lists, and taking an initial
+-- segment.
+--
+-- >>> myconcat = foldr (\x z -> foldr (:) z x) []
+-- >>> take 15 $ myconcat $ map (\i -> [0..i]) [0..]
+-- [0,0,1,0,1,2,0,1,2,3,0,1,2,3,4]
+--
+-- Of course in this case another way to achieve the same result is via a
+-- list comprehension:
+--
+-- > myconcat xss = [x | xs <- xss, x <- xs]
 
 --------------