Haskell中foldl与foldr的行为差异疑问

核心问题出在lambda的参数顺序和foldl的要求不匹配。

先明确两个折叠函数的函数参数定义：

• foldr的函数要求是：元素 -> 累加值 -> 结果，你的lambda (\x acc -> acc + x*2)刚好符合这个顺序，所以计算正常。
• foldl的函数要求是：累加值 -> 元素 -> 结果，你写的lambda把参数顺序搞反了，导致每次调用时把前一次的累加结果当成了x，把当前列表元素当成了acc，最终出现了幂次累加的结果。

用具体列表[1,2,3]拆解计算过程：

foldr的正确计算过程 #

foldr (\x acc -> acc + x*2) 0 [1,2,3]
= (\x acc -> acc + x*2) 1 (foldr ... 0 [2,3])
= (foldr ... 0 [2,3]) + 1*2
  -- 展开foldr ... 0 [2,3]
  = (\x acc -> acc + x*2) 2 (foldr ... 0 [3]) + 2*2
    -- 展开foldr ... 0 [3]
    = (0 + 3*2) + 2*2
= (6 + 4) + 2 = 12

结果是所有元素的两倍之和，符合预期。

foldl的错误计算过程（参数顺序颠倒） #

foldl (\x acc -> acc + x*2) 0 [1,2,3]
-- 第一步：用初始值0和第一个元素1调用lambda，此时x=0，acc=1
= foldl ... (1 + 0*2) [2,3]
= foldl ... 1 [2,3]
-- 第二步：用当前累加值1和第二个元素2调用lambda，此时x=1，acc=2
= foldl ... (2 + 1*2) [3]
= foldl ... 4 [3]
-- 第三步：用当前累加值4和第三个元素3调用lambda，此时x=4，acc=3
= foldl ... (3 + 4*2) []
= 11

最终结果11 = 1*4 + 2*2 +3*1，也就是每个元素从右往左数的位置（从0开始）对应2的幂次乘以元素值的和——这就是你看到的奇怪结果的原因。

修正方法 #

把lambda的参数顺序反过来，改成(\acc x -> acc + x*2)，再用foldl计算：

foldl (\acc x -> acc + x*2) 0 [1,2,3]
= foldl ... (0 + 1*2) [2,3]
= foldl ... 2 [2,3]
= foldl ... (2 + 2*2) [3]
= foldl ... 6 [3]
= foldl ... (6 +3*2) []
=12

结果就和foldr一致了。

内容的提问来源于stack exchange，提问作者placeholder223