Haskell，Foldr和foldl
我一直试图把我的头绕在foldr上并折叠很长时间，而且我已经决定了下面的问题应该为我解决。 假设您将以下列表[1,2,3]传递给以下四个函数：
a = foldl (xs y -> 10*xs -y) 0
b = foldl (xs y -> y - 10 * xs) 0
c = foldr (y xs -> y - 10 * xs) 0
d = foldr (y xs -> 10 * xs -y) 0
结果将分别为-123,83,281和-321。
为什么会这样？ 我知道，当你将[1,2,3,4]传递给定义为的函数时
f = foldl (xs x -> xs ++ [f x]) []
它被扩展为（（（[] ++ [1]）++ [2]）++ [3]）++ [4]
同样，上述函数a，b，c和d会被扩展到什么地方？
我认为Haskell Wiki的折页上的两个图像很好地解释了它。
由于您的操作不可交换， foldr和foldl的结果将不会相同，而在交换操作中它们会：
Prelude> foldl1 (*) [1..3]
6
Prelude> foldr1 (*) [1..3]
6
使用scanl和scanr得到包括中间结果列表是为了看看会发生什么的好方法：
Prelude> scanl1 (*) [1..3]
[1,2,6]
Prelude> scanr1 (*) [1..3]
[6,6,3]
所以在第一种情况下我们有（（（1 * 1）* 2）* 3），而在第二种情况下它是（1 *（2 *（1 * 3）））。
foldr是一个非常简单的功能的想法：它结合了两个参数的函数，得到一个起点，一个列表，并计算调用以这种方式列表中的函数的结果。
以下是关于如何想象在foldr调用过程中发生的事情的一个很好的暗示：
foldr (+) 0 [1,2,3,4,5]
=> 1 + (2 + (3 + (4 + (5 + 0))))
我们都知道[1,2,3,4,5] = 1:2:3:4:5:[] 。 你所需要做的就是将[]与出发点和:用我们使用的任何函数替换。 当然，我们也可以用相同的方式重建列表：
foldr (:) [] [1,2,3]
=> 1 : (2 : (3 : []))
如果我们看一下签名，我们可以更好地理解函数内部发生的事情：
foldr :: (a -> b -> b) -> b -> [a] -> b
我们看到，函数首先会从列表中，则蓄能器的元素，并返回下蓄电池将是什么。 有了这个，我们可以编写我们自己的foldr函数：
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f a [] = a
foldr f a (x:xs) = f x (foldr f a xs)
你在那里; 你应该有一个更好的想法，如何foldr的工作，这样你就可以应用到你的问题上面。
可以将fold*函数看作循环传递给它的列表，从列表的末尾（ foldr ）开始，或者从列表的开始（ foldl ）开始。 对于找到的每个元素，它都会将此元素和累加器的当前值传递给您已写为lambda函数的内容。 无论这个函数返回什么，都将用作下一次迭代中累加器的值。
稍微改变你的符号（ acc而不是xs ）以表示更清晰的含义，对于第一个左边的折叠
a = foldl (acc y -> 10*acc - y) 0 [1, 2, 3]
= foldl (acc y -> 10*acc - y) (0*1 - 1) [2, 3]
= foldl (acc y -> 10*acc - y) -1 [2, 3]
= foldl (acc y -> 10*acc - y) (10*(-1) - 2) [3]
= foldl (acc y -> 10*acc - y) (-12) [3]
= foldl (acc y -> 10*acc - y) (10*(-12) - 3) []
= foldl (acc y -> 10*acc - y) (-123) []
= (-123)
对于你的第一个正确的折叠（注意累加器在lambda函数的参数中占据不同的位置）
c = foldr (y acc -> y - 10*acc) 0 [1, 2, 3]
= foldr (y acc -> y - 10*acc) (3 - 10*0) [1, 2]
= foldr (y acc -> y - 10*acc) 3 [1, 2]
= foldr (y acc -> y - 10*acc) (2 - 10*3) [1]
= foldr (y acc -> y - 10*acc) (-28) [1]
= foldr (y acc -> y - 10*acc) (1 - 10*(-28)) []
= foldr (y acc -> y - 10*acc) 281 []
= 281