explain how to use this specific function of foldl

Question

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

foldl is folds the list up from the left side. So first we get the acc=0 and put the list xs to x ,then doing the function ->acc+x.After calculation, we get the new acc which is equal to acc+x. But why is that? I think this result of acc+x is the new value of x based on the function x->acc+x.

Answer 1

Let's take a look at your definition of sum

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

Let's also take a peek at foldl's signature:

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

Hmm, ok, what do we have to feed foldl in order to get the value at the very, very end (->a)?

1. It needs a curried function (a->b->a). All though not accurate, for brevity's sake, we'll say its a function that takes two arguments (but you and I know that really, it takes one argument and returns another function that takes one argument).

2. It needs a value of type a. Notice that our curried function from Step 1. takes something of type a and returns something of type a. Interesting...hmmm...

3. It needs a list of type b. Notice our curried function from Step 1 takes, as well as something of type a, something of type b.

So, do we give it what it wants?

1. We give it (\acc x -> acc + x). This is an anonymous function, or lambda, that takes two arguments, (remember, it's curried, though), acc and x, and return's their sum.

2. We give it 0 as our starting value

3. We give it xs as the list to fold.

Ok dokie. So, let's just let foldl work its Haskell magic. Let's imagine we called sum [1,2,3]

foldl calls our function (\acc x -> acc + x), using 0 for acc and the first value of xs, 1.

 0 + 1

This result does not get stored away in acc or x, since they are just arguments in our little lambda function. foldl is going to use that value (see SanSS's answer for the specific implementation).

Remember that the result of our lambda function is the same type as the first parameter? foldl can use that previous sum and pass it back to the lambda function, along with the second element.

(0 + 1) + 2

And again until it has done this for all the elements:

((0 + 1) + 2) + 3
6

As pointed out by Dan, this is the same if you had done:

sum xs = foldl (+) 0 xs

You can tell more easily with this function that we aren't just 'setting' some variable and adding onto it.

Hope this helps.

---

Side note: For your definition of sum, you don't have to explicitly state that sum takes xs. You could leave it as:

sum = foldl (\acc x -> acc + x) 0

This takes advantage of currying, because if we provide foldl just its first two arguments -- a curried function like (a->b->a) and a value of type a -- what do we get?

[b] -> a

A function that takes a list of type b and returns a value of type a! This is called pointfree style. Just something to consider :-)

Answer 2

From your question, it sounds like you don't understand how the lambda function (\acc x -> acc + x) works here.

The function is not x->acc+x, but acc x->acc + x. In fact, you could rewrite the "sum" equation as

sum xs = foldl (+) 0 xs

Since (\acc x -> acc + x) is the same as (+)

I suggest you (re)read http://learnyouahaskell.com/higher-order-functions#lambdas

Answer 3

You should look at the definition of foldl:

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

foldl recieves a funcion which takes 2 arguments, a value (the "starter value" or accumulator) and a list. In case the list is empty it returns the current calculation. If the case is not empty then it calls recursively with the same function as function, the accumulator is the result of the invocation of the function using the accumulator as the first argument and the first element of the list as the second argument and the tail of the list is used as the list for the recursive call.

So the lambda function used in sum becomes quite clear it takes acc as first argument and the element of the list as second argument and return the sum of both.

The result of the invocations for:

sum [1,2,3] = ((0 + 1) + 2) + 3 = 6