Haskell函數foldl（\ x y - > x * 2 + y * 2）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(1,f(2, f(3,0)))而不是f(3,f(2, f(1,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