foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
我正試圖圍繞這兩個功能展開思考。我有兩個問題。一是關于功能f。一般來說，
foldr f v xs
f可以訪問第一個元素xs和遞回處理的尾部。這里：
foldl f v xs
f可以訪問 xs 的最后一個元素和遞回處理的尾部。
這是一種有用（且正確）的思考方式嗎？
我的第二個問題與折疊“右”或“左”有關。在很多地方，他們說 foldr“從右邊開始”。例如，如果我擴展運算式
foldr ( ) 0 [1,2,3]
我明白了
( ) 1 (foldr ( ) 0 [2,3])
所以，我看到它是“從串列的左邊開始”。第一個元素和遞回處理的尾部是函式的引數。有人可以對這個問題有所了解嗎？
編輯：我的問題之一是f傳遞給的函式fold；鏈接的答案沒有解決這一點。
uj5u.com熱心網友回復：
“從右邊開始”是很好的基本直覺，但它也可能會產生誤導，正如您剛剛發現的那樣。事實上，Haskell 中的串列是單鏈接的，我們只能直接訪問一側，因此在某種意義上，Haskell 中的每個串列操作都是從左側“開始”的。但它從那里做什么才是重要的。讓我們完成擴展您的foldr示例。
foldr ( ) 0 [1, 2, 3]
1 foldr 0 [2, 3]
1 (2 foldr 0 [3])
1 (2 (3 foldr 0 []))
1 (2 (3 0))
現在對foldl.
foldl ( ) 0 [1, 2, 3]
foldl ( ) (0 1) [2, 3]
foldl ( ) ((0 1) 2) [3]
foldl ( ) (((0 1) 2) 3) []
((0 1) 2) 3
在這種foldr情況下，我們直接進行遞回呼叫，因此我們將頭部作為累加函式的引數，然后將另一個引數作為遞回呼叫。
在這種foldl情況下，我們通過更改累加器引數來進行遞回呼叫。由于我們更改的是引數而不是結果，因此評估的順序會顛倒過來。
不同之處在于括號“關聯”的方式。在這種foldr情況下，括號關聯到右側，而在這種foldl情況下，它們關聯到左側。同樣，“初始”值在 的右側foldr和左側foldl。
在 Haskell 的串列中使用折疊的一般建議是這樣的。
foldr如果您想要尊重串列結構的惰性評估，請使用。由于foldr它在函式呼叫內部進行遞回，所以如果折疊函式恰好被保護（即通過資料建構式），那么我們的foldr呼叫被保護。例如，我們可以用foldr另一個無限串列有效地構造一個無限串列。使用嚴格的左折疊
foldl'（注意'最后的），用于您希望操作嚴格的情況。foldl'在繼續之前強制折疊的每一步都變成弱頭部正常形式，防止重擊積聚。因此，whilefoldl將構建整個內部運算式，然后可能在最后對其進行評估，它將在foldl'我們進行時完成作業，這在大型串列上節省了大量記憶體。不要
foldl在串列中使用。獲得的懶惰foldl幾乎沒有用處，因為從左折疊中獲得任何有用的唯一方法是強制整個折疊無論如何，在內部建立 thunk 是沒有用的。
對于其他不右偏的資料結構，規則可能不同。所有這些都是在假設您Foldable是 Haskell 串列的情況下運行的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/477445.html
上一篇：模板Haskell決議型別別名