9

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?

Cœur
  • 37,241
  • 25
  • 195
  • 267
martin
  • 1,102
  • 2
  • 12
  • 20

1 Answers1

17

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.

amalloy
  • 89,153
  • 8
  • 140
  • 205
  • Why do `foldr (flip f)` and `foldl` always yield the same result for the non-commutative `-` operation, but `foldl (flip f)`/`foldr` do not? –  Jul 02 '17 at 10:13
  • 2
    @ftor Because `-` follows the identity `(a-b)-c = (a-c)-b`. In general, all four results may be different, but not with `-`. – isaacg Jul 02 '17 at 12:46
  • 2
    @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)`. – dfeuer Jul 02 '17 at 19:50
  • 2
    Another one that always holds: `foldr c n (reverse xs) = foldl (flip c) n xs`. – dfeuer Jul 02 '17 at 19:53