1

次の関数が無限ループを引き起こす理由がわかりません。

import Data.List

isTrue = foldl' (&&) False (repeat False)
4

2 に答える 2

13

foldlとはどちらfoldl'も、部分的な結果を生成する前にリスト全体を調べなければならないような方法で定義されています (実際、そうでないような定義方法はありません)。したがって、どちらも無限リストでは機能しません。

于 2013-03-10T19:56:28.567 に答える
5

これらはプレーンfoldlとrepeat：の定義です。

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

repeat :: a -> [a]
repeat a = a : repeat a

さて、あなたの定義を試してみるとどうなりますisTrueか？（もちろん、怠惰foldlに適応しますが、これはあなたと同じ問題があります。）

foldl (&&) False (repeat False)
    == foldl (&&) False (False : repeat False)
    == foldl (&&) (False && False) (repeat False)

これが重要な瞬間です。ここからどのように評価を続けますか？まあ、それはfoldlサンクなので、2つのfoldl方程式のどちらを使用するかを理解する必要があります。1つは[]パターンを使用するか、もう1つはを使用しx:xsます。これは、repeat Falseそれが空のリストであるかペアであるかを強制的に確認する必要があることを意味します。

    == foldl (&&) (False && False) (False : repeat False)
    == foldl (&&) ((False && False) && False) (repeat False)

...そしてそれはこれを続けます。基本的に、foldlが発生した場合にのみ終了でき、を生成することは[]ありません。repeat[]

    == foldl (&&) ((False && False) && False) (False : repeat False)
    == foldl (&&) (((False && False) && False) && False) (repeat False)
    ...

strictを使用するfoldl'ということは、False && False用語がちょうどFalseに短縮されることを意味します。したがって、コードは一定のスペースで実行されます。[]しかし、それはそれが決して来ないであろうを見るまでそれでも続きます：

foldl' f z [] = z
foldl' f z (x:xs) = 
    let z' = f z x 
    in z' `seq` foldl' f z' xs

foldl' (&&) False (repeat False)
    == foldl' (&&) False (False : repeat False)
    == let z' = False && False in z' `seq` foldl' (&&) z' (repeat False)

       -- We reduce the seq by forcing z' and substituting its result into the 
       -- its second argument.  Which takes us right back to where we started...
    == foldl' (&&) False (repeat False)
    ...

これらの関数には、アキュムレータが。以外のものになることはないことを確認できるスマート機能はありませんFalse。 foldl'どちらがどのように機能するかについては何も知りませ(&&)んrepeat False。それが知っているのはリストだけであり、それは空のリストでのみ終了します。

厳格な言語から来た人々にとって、Haskellのトリッキーなことの1つは、そのような言語では、左の折り目は末尾再帰であり、したがって一定のスペースで実行されるため、左の折り目は右の折り目よりも「優れている」ことを学びました。フォールドは真の再帰的であり、長いリストでスタックを爆破します。

Haskellでは、怠惰のため、通常はその逆であり、それfoldlはfoldl'厄介なものですが、foldr'は「良い」ものです。たとえば、以下は終了します。

foldr (&&) False (repeat False)

なんで？の定義は次のfoldrとおりです。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z = []
foldr f z (x:xs) = f x (foldr f z xs)

ここでの2番目の方程式をfoldl;の方程式と比較してください。foldl'は末尾再帰ですが、foldr末尾呼び出しfは再帰foldr呼び出しを引数として渡します。これはf、;を再帰するかどうか、いつ再帰するかを選択できることを意味しますfoldr。2番目の引数が怠惰な場合f、結果が必要になるまで再帰は延期されます。そして、f2番目の引数を破棄した場合、再帰することはありません。

だから、私の例に適用されます：

foldr (&&) False (repeat False)
    == foldr (&&) False (False : repeat False)
    == False && foldr (&&) False (repeat False)
    == False

これで完了です。ただし、これ(&&)は最初の引数が厳密であるためにのみ機能し、最初の引数が。の場合は2番目の引数を破棄することに注意してくださいFalse。次のバリエーションは無限ループに入ります。

foldr (flip (&&)) False (repeat False)
于 2013-03-10T22:54:39.703 に答える