此問題中 myAny函數的代碼使用文件夾。當滿足謂詞時，它將停止處理無限列表。我用foldl重寫了它：myAny :: (a -> Bool) -> [a] -> BoolmyAny p list = foldl step False list where step acc item = p item || acc（請注意，step函數的參數已正確反轉。）但是，它不再停止處理無限列表。我試圖按照Apocalisp的回答來跟蹤函數的執行：myAny even [1..]foldl step False [1..]step (foldl step False [2..]) 1even 1 || (foldl step False [2..])False || (foldl step False [2..])foldl step False [2..]step (foldl step False [3..]) 2even 2 || (foldl step False [3..])True || (foldl step False [3..])True但是，這不是函數的行為方式。這怎么了
3 回答
富國滬深
TA貢獻1790條經驗 獲得超9個贊
如何fold小號的不同似乎是混亂的常見來源，所以這里的一個更一般的概述：
考慮[x1, x2, x3, x4 ... xn ]使用某些函數f和seed 折疊n個值的列表z。
foldl 是：
左聯想：f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
尾遞歸：遍歷列表，然后產生值
惰性：需要結果之前，不會評估任何內容
向后：foldl (flip (:)) []反轉列表。
foldr 是：
右聯想：f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
遞歸到參數中：每次迭代都適用f于下一個值以及折疊其余列表的結果。
惰性：需要結果之前，不會評估任何內容
轉發：foldr (:) []返回不變的列表。
有一個稍微含蓄點在這里，游人們有時高達：由于foldl是向后的每個應用程序f被添加到外界的結果; 并且由于它是惰性的，因此在需要結果之前不會進行任何評估。這意味著，要計算結果的任何部分，Haskell首先遍歷整個列表，以構建嵌套函數應用程序的表達式，然后評估最外部的函數，并根據需要評估其參數。如果f始終使用第一個參數，則意味著Haskell必須一直遞歸到最內層術語，然后向后計算的每個應用程序f。
這顯然與大多數函數程序員所知道并喜歡的高效尾遞歸相去甚遠！
實際上，即使foldl從技術上講，它是尾遞歸的，但由于整個結果表達式是在求值之前構建的，因此foldl可能導致堆棧溢出！
另一方面，請考慮foldr。它也很懶，但是因為它向前運行，所以每個的應用程序f都會添加到結果的內部。因此，為了計算結果，Haskell構造了一個函數應用程序，其第二個參數是折疊列表的其余部分。如果if f在其第二個參數（例如，數據構造函數）中是lazy，則結果將是lazy遞增的，僅當需要評估結果的某些部分時才計算折疊的每一步。
因此，我們可以看到為什么foldr有時在foldl不行的情況下無法工作的原因：前者可以將一個無限列表懶惰地轉換為另一個懶惰的無限數據結構，而后者必須檢查整個列表以生成結果的任何部分。另一方面，foldr對于立即需要兩個參數的函數，例如(+)，可以像一樣工作（或更確切地說，不起作用），類似于foldl在評估它之前構建一個巨大的表達式。
因此，需要注意的兩個重要點是：
foldr 可以將一種惰性遞歸數據結構轉換為另一種。
否則，懶惰折疊將在大型或無限列表上崩潰并導致堆棧溢出。
您可能已經注意到，聽起來foldr一切foldl都可以做，還有更多。這是真的！實際上，foldl幾乎沒有用！
但是，如果我們想通過折疊很大（但不是無限）的列表來產生非惰性結果呢？為此，我們需要一個嚴格的fold，這是標準庫提供的：
foldl' 是：
左聯想：f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
尾遞歸：遍歷列表，然后產生值
嚴格：每個功能應用程序都將一路評估
向后：foldl' (flip (:)) []反轉列表。
因為foldl'是strict，為了計算結果，Haskell將在每一步求值 f，而不是讓左參數積累一個巨大的，未求值的表達式。這為我們提供了我們想要的通常有效的尾部遞歸！換一種說法：
foldl' 可以有效地折疊大列表。
foldl' 將掛在無限列表上的無限循環中（不會導致堆棧溢出）。
Haskell Wiki上也有討論此內容的頁面。
不負相思意
TA貢獻1777條經驗 獲得超10個贊
myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]
等等
直觀上，foldl它總是在“外部”或“左側”，因此它首先被擴展。廣告無限。
慕碼人2483693
TA貢獻1860條經驗 獲得超9個贊
您可以Haskell的文檔中看到這里是與foldl是尾遞歸，如果傳入一個無限列表，因為它返回一個值之前稱自己的下一個參數將永遠不會結束......
- 3 回答
- 0 關注
- 685 瀏覽
添加回答
舉報
0/150
提交
取消