The missing folds

Question

If you want to fold a list, I see four ways to do it.

Fold from the right of the list, with the recursive term on the right

foldrr (-) 100 [1..10] = 1 - (2 - (3 - (4 - (5 - (6 - (7 - (8 - (9 - (10 - (100)))))))))) = 95

foldrr :: (a -> b -> b) -> b -> [a] -> b
foldrr step zero (x:xs) = step x (foldrr step zero xs)
foldrr _    zero []     = zero

Fold from the right of the list, with the recursive term on the left

foldrl (-) 100 [1..10] = ((((((((((100) - 10) - 9) - 8) - 7) - 6) - 5) - 4) - 3) - 2) - 1 = 45

foldrl :: (a -> b -> a) -> a -> [b] -> a
foldrl step zero (x:xs) = step (foldrl step zero xs) x
foldrl _    zero []     = zero

Fold from the left of the list with the recursive term on the right

foldlr (-) 100 [1..10] = 10 - (9 - (8 - (7 - (6 - (5 - (4 - (3 - (2 - (1 - (100)))))))))) = 105

foldlr :: (a -> b -> b) -> b -> [a] -> b
foldlr step zero (x:xs) = foldlr step (step x zero) xs
foldlr _    zero []     = zero

Fold from the left of the list with the recursive term on the left

foldll (-) 100 [1..10] = ((((((((((100) - 1) - 2) - 3) - 4) - 5) - 6) - 7) - 8) - 9) - 10 = 45

foldll :: (a -> b -> a) -> a -> [b] -> a
foldll step zero (x:xs) = foldll step (step zero x) xs
foldll _    zero []     = zero

---

Only two of these folds made it into Prelude as foldr and foldl. Was there any reason to just include two folds, and why those two?

Ferris

Answer 1

foldrl and foldlr don't add any expressive power: they are just the same as the other two folds but with the folding function flipped.

foldrl f = foldr (flip f)
foldlr f = foldl (flip f)

-- Or this, if you prefer
foldrl = foldr . flip
foldlr = foldl . flip

But it is not so easy to define foldl in terms of foldr, so providing them both is useful.

Smoothen

Why do foldr (flip f) and foldl always yield the same result for the non-commutative - operation, but foldl (flip f)/foldr do not? – Artimas

@ftor Because - follows the identity (a-b)-c = (a-c)-b. In general, all four results may be different, but not with -. – Hypophosphite

@ftor, there is a general identity of that nature: foldl f b xs = foldr (flip f) b (reverse xs). For finite lists, it's also true that foldr c n xs = foldl (flip c) n (reverse xs). – Sluice

Another one that always holds: foldr c n (reverse xs) = foldl (flip c) n xs. – Sluice