累加器中的累加器

Question

在Haskell Wikibook中,foldr实现如下:

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

声明累加器的初始值被设置为参数.但据我了解,acc是操作的标识值(例如0表示sum或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？歇斯底里的葡萄干？一个谎言给孩子？我不确定.

编辑:我还要指出GHC实现的foldr使用z(大概为零)而不是acc.