Creased battery

Question

In Haskell Wikibook, foldr is implemented as follows:

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

It is stated that the initial value of the battery is specified as an argument. But, as I understand it, acc is the identity value for the operation (for example, 0 for the sum or 1 for the 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 a battery, implying that it changes or accumulates the value step by step?

I see that the battery matters in the left fold, for example foldl, but is the wikibook explanation wrong and only for symmetry, in which case is it wrong?

Answer 1

Consider evaluating a simple foldr expression based on the (correct) definition you specified:

  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're right: acc doesn't really “accumulate” anything. It never takes a value other than 0 .

Why is it called "acc" if it is not a battery? Similar to foldl ? Hysterical raisins ? A lie to children ? I'm not sure.

Edit: I will also point out that the GHC foldr implementation uses z (supposedly for zero), not acc .

Answer 2

acc doesn't actually accumulate anything in the case of foldr , as indicated.

I would add that without it, it is not clear what should happen when the input is an empty list.

It also changes the signature of type f , restricting the functions that can be used.

eg:

 foldr' :: (a -> a -> a) -> [a] -> a foldr' f [] = error "empty list???" foldr' f (x:[]) = x foldr' f (x:xs) = fx (foldr' f xs)