你怎麼知道何時使用摺疊和何時使用摺疊權？

Question

我知道摺疊左邊會產生左傾的樹木，而右折可以產生右傾的樹木，但是當我達到摺疊的時候，我有時會發現自己陷入了頭痛的誘因之中，試圖確定是哪一種的倍數是合適的。我通常最終解開整個問題，並逐步執行摺疊函數，因爲它適用於我的問題。

所以，我想知道的是：

• 是什麼的一些經驗法則來確定是否留下來折或摺疊吧？
• 鑑於我面臨的問題，我該如何快速決定使用哪種摺疊類型？

在Scala by Example（PDF）中有一個使用摺疊編寫一個稱爲flatten的函數的示例，該函數將元素列表鏈接到單個列表中。在這種情況下，正確的選擇是正確的選擇（考慮到列表連接的方式），但是我必須考慮一點才能得出結論。

由於在功能性編程中摺疊是一種常見的行爲，我希望能夠迅速而自信地做出這些決定。那麼......任何提示？

Answer 1

您可以將摺疊成一個管道符符號（寫入之間）：

這個例子倍使用累加器功能x

fold x [A, B, C, D] 

從而等於

A x B x C x D 

現在你只需要推斷你的操作符的相關性（通過放置圓括號！）。

如果你有一個左結合運營商，您將設置括號這樣

((A x B) x C) x D 

在這裏，你使用左摺疊。示例（哈斯克爾式的僞代碼）

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative 

如果你的操作是右結合（右折），括號將設置這樣的：

A x (B x (C x D)) 

例如：缺點運營商

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3] 

一般來說，算術運算符（大多數運算符）是左關聯的，所以foldl更廣泛。但在其他情況下，中綴記法+圓括號非常有用。

Answer 2

它也值得注意（我意識到這是明顯的一點），在交換運算符的情況下，兩者幾乎是等價的。在這種情況下，一個與foldl可能是更好的選擇：

與foldl： (((1 + 2) + 3) + 4)可以計算出每一個操作和執行的累加值向前

foldr相似： (1 + (2 + (3 + 4)))需要一個堆棧幀計算之前打開的1 + ?和2 + ?3 + 4，那麼它需要返回併爲每個計算。

我不是足夠的功能語言或編譯器優化的專家，說這是否會實際上有所作爲，但它確實似乎更清潔使用foldl與交換操作符。

Answer 3

Olin Shivers通過說「foldl是基本列表迭代器」和「foldr是基本列表遞歸運算符」來區分它們。如果你看一下如何與foldl工作：

((1 + 2) + 3) + 4 

你可以看到蓄電池（如在尾遞歸迭代）在建。相比之下，foldr相似收益：

1 + (2 + (3 + 4)) 

在這裏你可以看到遍歷的基本情況4，建立了從那裏的結果。

所以我提出了一條經驗法則：如果它看起來像一個列表迭代，那麼可以簡單地用尾遞歸形式來編寫，foldl就是要走的路。

但實際上，這可能是最明顯的從您正在使用的操作符的關聯性。如果他們是左聯合的，請使用foldl。如果它們是正確關聯的，請使用foldr。

Answer 4

其他海報已經給出了很好的答案，我不會重複他們已經說過的話。正如你在你的問題中給出了一個Scala例子，我將給出一個Scala特定的例子。正如Tricks已經說過，一個foldRight需要保留n-1堆棧幀，其中n是您的列表的長度，這很容易導致堆棧溢出 - 甚至連尾部遞歸都不能使你免於此。

甲List(1,2,3).foldRight(0)(_ + _)將減少到：

1 + List(2,3).foldRight(0)(_ + _)  // first stack frame 
    2 + List(3).foldRight(0)(_ + _)  // second stack frame 
     3 + 0       // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well) 

List(1,2,3).foldLeft(0)(_ + _)同時將減少到：

(((0 + 1) + 2) + 3) 

可迭代計算，如在implementation of List完成。

在一個嚴格評估的語言斯卡拉，foldRight可以輕鬆地吹大堆列表，而foldLeft不會。

例：因此

scala> List.range(1, 10000).foldLeft(0)(_ + _) 
res1: Int = 49995000 

scala> List.range(1, 10000).foldRight(0)(_ + _) 
java.lang.StackOverflowError 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRig...

我的經驗法則是 - 對於不具有特定的關聯性，始終使用foldLeft，至少在斯卡拉運營商。否則，請與答案中給出的其他建議;）。