Haskell 函数 foldl (\x y -> x2 + y2) 0 行为

Question

我遇到了一个问题。这两个函数有什么区别：

foldl (\x y -> x*2 + y*2) 0 [1,2,3] = 22
foldr (\x y -> x*2 + y*2) 0 [1,2,3] = 34

foldl (\x y -> x*2 + y*2) 0 [1,2,3] ⇒ f( f( f(0,1),2 ),3 )
foldr (\x y -> x*2 + y*2) 0 [1,2,3] ⇒ f( 3,f( 2, f(1,0) ) )

其中 f = \x y -> x*2 + y*2.

我理解 foldl 的结果：

x = f(0,1) = 2
y = f(x,2) = 8
z = f(y,3) = 22

但为什么 foldr 在每一步的结果后求和？

2 + 8 + 22 = 34

Answer 1

您的 foldr 评价倒退了。它应该是这样的：

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

相比之下，foldl 评估（在您的问题中是正确的）看起来像

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

如果您认为列表 [1,2,3] 与 1:2:3:[] 相同，那么这张 foldr 的图表可能会有所帮助：

Answer 2

您对 foldr 的定义有点偏差。而不是 f( 3,f( 2, f(1,0) ) )，它应该是 f( 1,f( 2, f(3,0) ) ).

foldl f z [1,2,3] = ((0 `f` 1) `f` 2) `f` 3
                  = ((0*2 + 1*2) `f` 2) `f` 3
                  = (2 `f` 2) `f` 3
                  = (2*2 + 2*2) `f` 3
                  = 8 `f` 3
                  = 8*2 + 3*2
                  = 22

foldr f z [1,2,3] = 1 `f` (2 `f` (3 `f` 0))
                  = 1 `f` (2 `f` (3*2 + 0*2))
                  = 1 `f` (2 `f` 6)
                  = 1 `f` (2*2 + 6*2)
                  = 1 `f` 16
                  = 1*2 + 16*2
                  = 34

Haskell 函数 foldl (\x y -> x2 + y2) 0 行为

Haskell function foldl (\x y -> x2 + y2) 0 behavior

haskell

fold

Haskell 函数 foldl (\x y -> x*2 + y*2) 0 行为

Haskell function foldl (\x y -> x*2 + y*2) 0 behavior

haskell

fold

Haskell 函数 foldl (\x y -> x2 + y2) 0 行为

Haskell function foldl (\x y -> x2 + y2) 0 behavior