我看過different folds和folding in general以及其他幾個,他們解釋得很好。foldr和foldl進一步的解釋和例子
在這種情況下,我仍然遇到lambda工作方式的問題。
foldr (\y ys -> ys ++ [y]) [] [1,2,3]
難道有人會經歷這一步,並試圖向我解釋這一點。
而且foldl
也會如何工作。
我看過different folds和folding in general以及其他幾個,他們解釋得很好。foldr和foldl進一步的解釋和例子
在這種情況下,我仍然遇到lambda工作方式的問題。
foldr (\y ys -> ys ++ [y]) [] [1,2,3]
難道有人會經歷這一步,並試圖向我解釋這一點。
而且foldl
也會如何工作。
使用
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]
的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]
中間符號可能會更清楚在這裏。
讓我們開始定義:
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]
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)+ ...)浪費內存,然後對它進行評估。
第三個像第二個,但與另一個公式。
+1用於解釋語義並給出一個類比。迄今爲止的其他答案只給予正式的減少,這很重要,但對於概念層面的理解,恕我直言更重要。 – thSoft 2013-02-11 13:20:19