なぜこのHaskellコードは終了しないのですか？

Question

なぜ以下のHaskellコードが終了しない：

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

このようなものがない場合：

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

私には、それが終了していないのよりトラブルになりそうだ第二の発現です。何がHaskellの遅延評価の私の見解が悪いですの？

Answer 1

あなたの怠け者の理解は正しいと思いますが、foldrではありません。あなたは私たちが||が終了に到達するために「を探して」いるTrue（z）ができなくなりますご覧のように、あなたの表現

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

を見て、その「specification」

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

を見てみましょうリスト全体が消費されるまで達する。リストが無限であるので、それは起こりません。

実際に終了する例についても説明します。

Answer 2

False || (False || (False || ...))に展開し、2番目はTrue || (True || (True || ...))に展開します。 foldrの第2引数は、赤ん坊です。||の最も内側のアプリケーションに表示されます。最も外側のアプリケーションではないため、実際には到達することはできません。

Answer 3

手動foldrを展開する場合、問題は、非常に明白である：

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

だから、最終的なFalseを得るために、コードは、その（nonexistant）最後までリストを評価しなければなりませんでした。 2番目の例では、Trueを繰り返すので、短絡の評価が可能です。怠惰な評価から魔法を期待しないでください！

Answer 4

Aはまだあなたのために別の洞察力が||はHaskellでは可換ではないということです、それは偏ったです：

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

だから、数学とは異なり、||とflip (||)は異なる機能です。例えば。旧終了

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

を比較するが、後者はそうではありません。