foldl / foldr 查询

Question

我是Haskell的初学者，即使阅读了多个关于foldr / foldl的解释，我仍无法理解为什么下面的结果不同。有什么解释吗？

Prelude> foldl (\_ -> (+1)) 0 [1,2,3]
4
Prelude> foldr (\_ -> (+1)) 0 [1,2,3]
3

谢谢！

- Frank

---

欢迎来到stackoverflow.com！不需要添加签名，因为在您的问题底部会出现一个带有您姓名的框。 - fuz

Answer 1

这是因为在foldl中参数的顺序相反。比较它们的类型签名：

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

因此，你会发现，在使用foldl的代码中，你反复增加累加器，而忽略了列表。但在使用foldr的代码中，你甚至没有触及累加器，而只是增加了列表的元素。由于最后一个元素是3，结果为3 + 1 = 4。

如果你使用字符列表，也就是字符串，你会更容易看到自己的错误：

ghci> foldr (\_ -> (+1)) 0 ['a','b','c']
3
ghci> foldl (\_ -> (+1)) 0 ['a','b','c']
:1:20:
    No instance for (Num Char)
      arising from the literal `0'
    Possible fix: add an instance declaration for (Num Char)
    In the second argument of `foldl', namely `0'
    In the expression: foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
    In an equation for `it':
        it = foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
ghci>

- fuz

Answer 2

在foldl的情况下，lambda函数将累加器作为第一个参数传递，将列表元素作为第二个参数传递。在foldr的情况下，lambda函数将列表元素作为第一个参数传递，将累加器作为第二个参数传递。

您的lambda函数忽略第一个参数，并将1添加到第二个参数中，因此在foldl的情况下，您将1添加到最后一个元素中，在foldr的情况下，您正在计算列表中的元素数量。

- pat

Answer 3

在foldl f中，累加器是f的左参数，您正在忽略它，因此返回1 +最后一个元素。使用foldr，累加器是右参数，因此对于每个项目，您都将累加器增加1，有效地给出了列表的长度。

f x y = y + 1

foldl f 0 [1, 2, 3]
= f (f (f 0 1) 2) 3 
= f ignored 3
= 3 + 1
= 4

foldr f 0 [1, 2, 3]
= f 1 (f 2 (f 3 0)))
= f ignored (f ignored (f ignored 0)))
= ((((0 + 1) + 1) + 1)
= 3

- hammar

Answer 4

区别在于两点：

• 你将一个输入丢弃到累加函数中，并对另一个应用常量函数。
• 两者之间累加函数的参数顺序不同。

使用左折叠，累加器是你要丢弃的参数，所以每次你都将 (+1) 应用于列表中的下一个项目，最终返回最后一个元素加一。

使用右折叠，累加器是你要保留的参数，所以每次你都将 (+1) 应用于前一个结果，该结果从0开始递增三次（对于列表中的每个项目）。

如果你使用更明显的不同输入值，可能更容易看出发生了什么：

Prelude> foldl (\_ -> (+1)) 100 [5,6,7]
8
Prelude> foldr (\_ -> (+1)) 100 [5,6,7]
103

再次强调，“最后一个参数加一”和“列表长度加初始值”。

- C. A. McCann

Answer 5

去掉柯里化和点式编程可能会有所帮助。你的两个表达式等价于：

foldl (\acc x ->   x + 1) 0 [1,2,3]
foldr (\x acc -> acc + 1) 0 [1,2,3]

当以这种方式查看时，结果应该更明显。

- TheIronKnuckle