11

我是 Haskell 的初学者，即使在阅读了几个对 foldr/foldl 的解释之后，我也无法理解为什么我会在下面得到不同的结果。解释是什么？

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

谢谢！

4

5 回答 5

8

那是因为参数的顺序被翻转了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:
    (Num Char) 没有实例
      由文字“0”引起
    可能的解决方法：为 (Num Char) 添加实例声明
    在'foldl'的第二个参数中，即'0'
    在表达式中： foldl (\_ -> (+ 1)) 0 ['a', 'b', 'c']
    在“它”的等式中：
        它 = foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c']
ghci>
于 2011-05-18T20:03:37.240 回答
7

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

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

于 2011-05-18T20:09:52.483 回答
6

在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
于 2011-05-18T20:02:11.707 回答
6

区别在于两点：

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

对于左折叠，累加器是您丢弃的参数，因此每次您应用(+1)到列表中的下一项并最终返回最后一个元素加一。

使用正确的折叠，累加器是您保留的参数，因此每次您应用(+1)到前一个结果时，它从 0 开始并增加三倍（对于列表中的每个项目）。

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

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

同样，“最后一个参数加一”和“列表长度加初始值”。

于 2011-05-18T20:03:33.920 回答
5

删除 currying 和 point free 样式可能会有所帮助。您的两个表达式等效于：

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

当这样看待时，结果应该看起来更明显

于 2011-12-30T02:48:22.390 回答