累加器在foldr相似

Question

在Haskell的维基教科书，如下foldr相似被实现。但据我所知，acc是操作的标识值（例如0表示总和或1表示产品），其值在执行函数期间不会改变。那么为什么它在这里和其他文本中被称为累加器，这意味着它会逐步改变或累积一个值？

我可以看到一个累加器在左边折叠中是相关的，比如foldl，但是wikibook解释是不正确的，只是对称性，在这种情况下它是错误的？

Answer 1

考虑您提供基于（正确的）定义一个简单的foldr表达的评价：

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 

所以，你是对的：acc并没有真正“积累”任何东西。它永远不会超过0以外的值。

为什么它称为“acc”，如果它不是累加器？与foldl相似？ Hysterical raisins？ A lie to children？我不确定。

编辑：我还要指出，foldr的GHC实现使用z（推测为零）而不是acc。

Answer 2

acc在foldr的情况下没有真正积累任何东西，正如已经指出的那样。

我想补充说，没有它，目前还不清楚当输入是一个空列表时应该发生什么。

它也改变了f的类型签名，限制了可以使用的功能。

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)