Haskell, Foldr, and foldl

Question

I've been trying to wrap my head around foldr and foldl for quite some time, and I've decided the following question should settle it for me. Suppose you pass the following list [1,2,3] into the following four functions:

a = foldl (\xs y -> 10*xs -y) 0
b = foldl (\xs y -> y - 10 * xs) 0
c = foldr (\y xs -> y - 10 * xs) 0
d = foldr (\y xs -> 10 * xs -y) 0

The results will be -123, 83, 281, and -321 respectively.

Why is this the case? I know that when you pass [1,2,3,4] into a function defined as

f = foldl (xs x -> xs ++ [f x]) []

it gets expanded to ((([] ++ [1]) ++ [2]) ++ [3]) ++ [4]

In the same vein, What do the above functions a, b, c, and d get expanded to?

Answer 1

I think the two images on Haskell Wiki's fold page explain it quite nicely.

Since your operations are not commutative, the results of foldr and foldl will not be the same, whereas in a commutative operation they would:

Prelude> foldl1 (*) [1..3]
6
Prelude> foldr1 (*) [1..3]
6

Using scanl and scanr to get a list including the intermediate results is a good way to see what happens:

Prelude> scanl1 (*) [1..3]
[1,2,6]
Prelude> scanr1 (*) [1..3]
[6,6,3]

So in the first case we have (((1 * 1) * 2) * 3), whereas in the second case it's (1 * (2 * (1 * 3))).

Answer 2

The fold* functions can be seen as looping over the list passed to it, starting from either the end of the list (foldr), or the start of the list (foldl). For each of the elements it finds, it passes this element and the current value of the accumulator to what you have written as a lambda function. Whatever this function returns is used as the value of the accumulator in the next iteration.

Slightly changing your notation (acc instead of xs) to show a clearer meaning, for the first left fold

a = foldl (\acc y -> 10*acc - y) 0              [1, 2, 3]
  = foldl (\acc y -> 10*acc - y) (0*1 - 1)      [2, 3]
  = foldl (\acc y -> 10*acc - y) -1             [2, 3]
  = foldl (\acc y -> 10*acc - y) (10*(-1) - 2)  [3]
  = foldl (\acc y -> 10*acc - y) (-12)          [3]
  = foldl (\acc y -> 10*acc - y) (10*(-12) - 3) []
  = foldl (\acc y -> 10*acc - y) (-123)         []
  = (-123)

And for your first right fold (note the accumulator takes a different position in the arguments to the lambda function)

c = foldr (\y acc -> y - 10*acc) 0              [1, 2, 3]
  = foldr (\y acc -> y - 10*acc) (3 - 10*0)     [1, 2]
  = foldr (\y acc -> y - 10*acc) 3              [1, 2]
  = foldr (\y acc -> y - 10*acc) (2 - 10*3)     [1]
  = foldr (\y acc -> y - 10*acc) (-28)          [1]
  = foldr (\y acc -> y - 10*acc) (1 - 10*(-28)) []
  = foldr (\y acc -> y - 10*acc) 281            []
  = 281

Answer 3

foldr is a really simple function idea: get a function which combines two arguments, get a starting point, a list, and compute the result of calling the function on the list in that way.

Here's a nice little hint about how to imagine what happens during a foldr call:

foldr (+) 0 [1,2,3,4,5]
=> 1 + (2 + (3 + (4 + (5 + 0))))

We all know that [1,2,3,4,5] = 1:2:3:4:5:[]. All you need to do is replace [] with the starting point and : with whatever function we use. Of course, we can also reconstruct a list in the same way:

foldr (:) [] [1,2,3]
=> 1 : (2 : (3 : []))

We can get more of an understanding of what happens within the function if we look at the signature:

foldr :: (a -> b -> b) -> b -> [a] -> b

We see that the function first gets an element from the list, then the accumulator, and returns what the next accumulator will be. With this, we can write our own foldr function:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f a []     = a
foldr f a (x:xs) = f x (foldr f a xs)

And there you are; you should have a better idea as to how foldr works, so you can apply that to your problems above.