Menu
In the Haskell Wikibook, foldr is implemented as follows:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)
It is stated that the initial value of the accumulator is set as an argument. But as I understand it, acc is the identity value for the operation (e.g. 0 for sum or 1 for product) and its value does not change during the execution of the function. Why then is it referred to here and in other texts as an accumulator, implying that it changes or accumulates a value step by step?
I can see that an accumulator is relevant in a left fold, such as foldl, but is the wikibook explanation incorrect, and only for symmetry, in which case it is wrong?
396
a starting value (in this case 0) for the accumulator (acc), and a list (in this case lst) to fold up. The binary function is repeatedly applied to the current accumulator value and a list element, in order, and produces a new current accumulator value.
To recap, with foldr , the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl , the function argument takes a default value, the first element of the list, and returns a new default value.
Difference Between foldl and foldr The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
So we can see why foldr sometimes works on infinite lists when foldl doesn't: The former can lazily convert an infinite list into another lazy infinite data structure, whereas the latter must inspect the entire list to generate any part of the result.
Consider the evaluation of a simple foldr expression based on the (correct) definition you provided:
foldr (+) 0 [1,2,3,4]
= 1 + foldr (+) 0 [2,3,4]
= 1 + 2 + foldr (+) 0 [3,4]
= 1 + 2 + 3 + foldr (+) 0 [4]
= 1 + 2 + 3 + 4 + foldr (+) 0 []
= 1 + 2 + 3 + 4 + 0
= 10
So you are right: acc doesn't really "accumulate" anything. It never takes on a value other than 0.
Why is it called "acc" if it isn't an accumulator? Similarity to foldl? Hysterical raisins? A lie to children? I'm not sure.
Edit: I'll also point out that the GHC implementation of foldr uses z (presumably for zero) rather than acc.
132
acc doesn't really accumulate anything in the case of foldr as has been pointed out.
I'd add that without it, it's not clear what should happen when the input is an empty list.
It also changes the type signature of f, limiting the functions that can be used.
E.g:
foldr' :: (a -> a -> a) -> [a] -> a
foldr' f [] = error "empty list???"
foldr' f (x:[]) = x
foldr' f (x:xs) = f x (foldr' f xs)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
