Haskell: Understanding the foldl function

Question

I am learning about folds from 'Learn You a Haskell for Great Good!' by Miran Lipovaca.

For the following example which uses foldl:

sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs 

ghci> sum' [3,5,2,1]
11

I understand that acc is the accumulator and x is the starting value (the first value from the list xs). I don't quite understand how 0 and xs are passed into the lambda function as parameters - how does the function know that the value of acc is 0 and the value of x is 3? Any insights are appreciated.

Answer 1

Recall the definition of foldl:

foldl f acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

Now, the best way to understand folds is to walk through the evaluation. So let's start with:

sum [3,5,2,1]
== foldl (\acc x -> acc + x) 0 [3,5,2,1]

The second line of the definition of the foldl function means this is equivalent to the following:

== foldl (\acc x -> acc + x) ((\acc x -> acc + x) 0 3) [5,2,1]

Now since the lambda expression is applied to parameters, 0 and 3 are passed in as acc and x:

== foldl (\acc x -> acc + x) (0+3) [5,2,1]

And the process repeats:

== foldl (\acc x -> acc + x) ((\acc x -> acc + x) (0+3) 5) [2,1]
== foldl (\acc x -> acc + x) ((0+3)+5) [2,1]
== foldl (\acc x -> acc + x) ((\acc x -> acc + x) ((0+3)+5) 2) [1]
== foldl (\acc x -> acc + x) (((0+3)+5)+2) [1]
== foldl (\acc x -> acc + x) ((\acc x -> acc + x) (((0+3)+5)+2) 1) []
== foldl (\acc x -> acc + x) ((((0+3)+5)+2)+1) []

At this point, evaluation continues according to the first line of the foldl definition:

== ((((0+3)+5)+2)+1)

So to answer your question directly: the function knows the values of acc and x simply because the definition of foldl passes their values to the function as parameters.

Answer 2

It would be helpful to look at how the foldl function is defined:

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

So, if the input list is empty then we just return the accumulator value a. However, if it's not empty then we loop. Within the loop, we update the accumulator value to f a x (i.e. we apply the lambda function f to the current accumulator value and the current element of the list). The result is the new accumulator value.

We also update the value of the list in the loop by removing its first element (because we just processed the first element). We keep processing the remaining elements of the list until there are no elements left, at which point we return the value of the accumulator.

The foldl function is equivalent to a for loop in imperative languages. For example, here's how we could implement foldl in JavaScript:

const result = foldl((acc, x) => acc + x, 0, [3,5,2,1]);

console.log(result);

function foldl(f, a, xs) {
    for (const x of xs) a = f(a, x);
    return a;
}

Hope that elucidates the foldl function.