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