foldr和foldl進一步的解釋和例子

Question

我看過different folds和folding in general以及其他幾個，他們解釋得很好。

在這種情況下，我仍然遇到lambda工作方式的問題。

foldr (\y ys -> ys ++ [y]) [] [1,2,3] 

難道有人會經歷這一步，並試圖向我解釋這一點。

而且foldl也會如何工作。

Answer 1

使用

foldr f z []  = z 
foldr f z (x:xs) = x `f` foldr f z xs 

而且

k y ys = ys ++ [y] 

讓我們解壓：

foldr k [] [1,2,3] 
= k 1 (foldr k [] [2,3] 
= k 1 (k 2 (foldr k [] [3])) 
= k 1 (k 2 (k 3 (foldr k [] []))) 
= (k 2 (k 3 (foldr k [] []))) ++ [1] 
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1] 
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1] 
= ((([]) ++ [3]) ++ [2]) ++ [1] 
= (([3]) ++ [2]) ++ [1] 
= ([3,2]) ++ [1] 
= [3,2,1] 

Answer 2

的foldr的定義是：

foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

所以這裏有一個循序漸進的例子逐步減少：

foldr (\y ys -> ys ++ [y]) [] [1,2,3] 
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3]) 
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1] 
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1] 
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1] 
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1] 
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1] 
= [] ++ [3] ++ [2] ++ [1] 
= [3,2,1] 

Answer 3

中間符號可能會更清楚在這裏。

讓我們開始定義：

foldr f z []  = z 
foldr f z (x:xs) = x `f` (foldr f z xs) 

爲了簡潔起見，讓我們寫g，而不是(\y ys -> ys ++ [y])。以下行是等效的：

foldr g [] [1,2,3] 
1 `g` (foldr g [] [2,3]) 
1 `g` (2 `g` (foldr g [] [3])) 
1 `g` (2 `g` (3 `g` (foldr g [] []))) 
1 `g` (2 `g` (3 `g` [])) 
(2 `g` (3 `g` [])) ++ [1] 
(3 `g` []) ++ [2] ++ [1] 
[3] ++ [2] ++ [1] 
[3,2,1] 

Answer 4

foldr相似是一件容易的事情：

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

它需要一個函數，它在某種程度上類似於（:)，

(:) :: a -> [a] -> [a] 

和的值類似於空列表[]，

[] :: [a] 

並在某個列表中替換每個：和[]。

它看起來像這樣：

foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e)) 

你能想象foldr相似的一些狀態機評價器，太：

f是過渡，

f :: input -> state -> state 

e是開始狀態。

e :: state 

foldr相似（foldRIGHT）運行狀態機與過渡f和啓動狀態E的輸入列表，開始在右端。想像中綴符號中的f作爲來自右邊的pacman。 foldl（foldLEFT）從-LEFT中執行相同的操作，但用中綴表示法編寫的過渡函數從右側開始輸入參數。所以機器從左端開始使用列表。由於嘴巴（b-> a-> b）而不是（a-> b-> b），Pacman消耗左側的開口 - 左側的列表。

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

爲了更清楚些，想象中的函數負過渡：

foldl (-) 100 [1]   = 99 = ((100)-1) 
foldl (-) 100 [1,2]  = 97 = ((99)-2) = (((100)-1)-2) 
foldl (-) 100 [1,2,3]  = 94 = ((97)-3) 
foldl (-) 100 [1,2,3,4] = 90 = ((94)-4) 
foldl (-) 100 [1,2,3,4,5] = 85 = ((90)-5) 

foldr (-) 100 [1]   = -99 = (1-(100)) 
foldr (-) 100 [2,1]  = 101 = (2-(-99)) = (2-(1-(100))) 
foldr (-) 100 [3,2,1]  = -98 = (3-(101)) 
foldr (-) 100 [4,3,2,1] = 102 = (4-(-98)) 
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102)) 

你可能想在的情況下，在列表中可以無限使用foldr相似，並在評價應該是懶惰：

foldr (either (\l (ls,rs)->(l:ls,rs)) 
       (\r (ls,rs)->(ls,r:rs)) 
    ) ([],[]) :: [Either l r]->([l],[r]) 

而且當您使用整個列表生成其輸出時，您可能想要使用foldl的嚴格版本，即foldl'。

foldl' (+) 0 [1..100000000] = 5000000050000000 
foldl (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci 
foldr (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci 

第一種 - 步驟一步：這可能是由於與懶惰評價相結合的極端長的列表有更好的表現，可能會阻止您不必堆棧溢出或超出內存異常（取決於編譯器） - 創建列表中的一個條目，對其進行評估並將其消耗。

第二個先創建一個很長的公式，用（（...（（0 + 1）+2）+3）+ ...）浪費內存，然後對它進行評估。

第三個像第二個，但與另一個公式。