爲什麼Haskell代碼不終止？

爲什麼下面的Haskell代碼不會終止：爲什麼Haskell代碼不終止？

foldr (||) True $ repeat False -- never terminates

當這樣的事情呢：

foldr (||) False $ repeat True -- => True

對我來說，這是第二個表達式，看起來是在不終止的更大的麻煩。我對Haskell懶惰評估的看法有什麼問題？

來源

2011-10-31 Steven Shaw

對於這類問題，您總是可以使用stepeval。它需要一秒鐘來解密，但可能會有所幫助。 http://bm380.user.srcf.net/cgi-bin/stepeval.cgi?expr=foldr+%28%7C%7C%29+True+%24+repeat+False – gatoatigrado

我寫了stepeval，並沒有評估這個表達式正確！它有一些錯誤，我擔心（在這種情況下，即使它仍然需要，它會忘記「讓」） –

我認爲你對懶惰的理解是正確的，但不適用於foldr。讓我們來看看它的「specification」

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

然後看看你的表情

foldr (||) True $ repeat False -- never terminates

正如你所看到的True（z），我們正在「尋找」讓||終止將不直到整個清單消耗完畢。這不會發生，因爲名單是無限的。

這也應該解釋爲實際終止的例子。

來源

2011-10-31 22:40:39 Tarrasch

的確，我誤解了foldr，不是懶惰的評價！ –

第一張展開爲False || (False || (False || ...))，第二張展開爲True || (True || (True || ...))。 foldr的第二個參數是一個紅色的鯡魚 - 它出現在||的最裏面的應用程序中，而不是最外面的，所以它實際上不可能達到。

來源

2011-10-31 22:40:31 mokus

的問題是很明顯的，如果手動展開foldr：

foldr (||) True $ repeat False == False || (False || (False (False || ... True)))

所以爲了得到最終False，代碼必須評估名單，直到它的（不存在的）結束。在你的第二個例子中，你重複True，因此短路評估是可能的。不要指望從懶惰評價魔術！

來源

2011-10-31 22:40:33 fuz

您在展開中交換了True和False。 –

@Daniel謝謝。這是在柏林的後期...... – fuz

一個又一個的洞察力你是||不是在Haskell交換，這是偏頗：

Prelude> undefined || True 
*** Exception: Prelude.undefined 
Prelude> True || undefined 
True

所以不像數學，||和flip (||)有不同的功能。例如。比較

foldr (||) False $ repeat True和foldr (flip (||)) False $ repeat True

前終止，但後者沒有。

來源

2011-11-01 19:48:43 nponeccop

謝謝。這對我來說確實是另一個驚喜！ –

爲什麼Haskell代碼不終止？

回答

相關問題