foldl/foldr查询

Question

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

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

谢谢!

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>

Answer 2

在这种foldl情况下,lambda作为第一个参数传递累加器,而第二个参数传递list元素.在这种foldr情况下,lambda作为第一个参数传递list元素,而第二个参数传递累加器.

你的lambda忽略了第一个参数,并在第二个参数foldl中加1 ,所以在你向最后一个元素添加1的foldr情况下,在这种情况下,你计算列表中的元素数.

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

Answer 4

不同之处在于两件事:

• 您正在丢弃累加函数的一个输入并将常量函数应用于另一个.
• 累加函数的参数顺序在两者之间是不同的.

使用左侧折叠,累加器是您丢弃的参数,因此每次您应用(+1)列表中的下一个项目并最终返回最后一个元素加一个.

使用右侧折叠,累加器是您保留的参数,因此每次应用于(+1)前一个结果时,该结果为0并且增加三次(对于列表中的每个项目).

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

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

再次,"最后一个参数加一个"和"列表长度加上初始值".

Answer 5

删除柯里化和无点风格可能会有所帮助。你的两个表达式相当于：

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

这样看来，结果应该显得更加明显