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情況下，拉姆達被傳遞蓄電池作爲第一個參數，以及列表元素作爲第二個。在foldr的情況下，lambda被傳遞給list元素作爲第一個參數，而accumulator作爲第二個參數。

您的lambda忽略第一個參數，並在第二個參數中加1，因此在foldl的情況下，您將向最後一個元素添加1，並在foldr的情況下計算列表中元素的數量。

Answer 2

在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 3

所不同的是，因爲兩件事情：

• 你丟棄一個輸入累積功能和應用功能不斷向其他。
• 兩者之間的累加函數的參數順序不同。

以左折，蓄電池是你放棄的說法，所以每次你在應用列表中的(+1)到下一個項目，並最終返回時的最後一個元素加一。

由於正確的摺疊，累加器就是您保留的參數，所以每次您將(+1)應用於之前的結果（從列表中的每個項目開始爲0開始並遞增3次）。

這可能是更容易地看到發生了什麼事情就到這裏，如果你使用更爲明顯不同的輸入值：

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

再次，「最後一個參數加一」和「列表，以及初始值的長度」。

Answer 4

這是因爲參數的順序在foldl中翻轉。比較其類型簽名：

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldr :: (a -> b -> b) -> b -> [a] -> b 

所以你看，在使用foldl你的代碼，你屢遞增累加器，忽略列表。但在foldr的代碼中，你甚至不碰累加器，而只是增加列表的元素。作爲最後一個元素是3，結果是3 + 1 = 4。

你可以看到你的misstake更容易，如果你使用的字符列表又名串來代替：

 
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 5

刪除咖喱和點自由風格可能會有所幫助。你的兩個表達式equivilent到：

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

當這樣的結果看應該