35

無限リストで正しく動作する Haskell コードがいくつかありますが、なぜうまく動作するのかわかりません。(無限リストを処理しなかった元のコードを変更して、オンラインの他のコードから何かを組み込むと、突然、それが機能することがわかりましたが、理由はわかりません)。

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldr step False list
   where
      step item acc = p item || acc

私の理解では、foldr はリスト内のすべての項目をループするということです (そして、おそらくその理解は不完全です)。もしそうなら、「ステップ」関数がどのように表現されているかは問題ではありません...コードは無限ループを処理できないはずです。

ただし、次のように動作します。

*Main Data.List> myAny even [1..]
True

私が理解するのを手伝ってください：なぜ??

4

4 に答える 4

50

Haskell が式を評価する方法を頭の中で少しトレースしてみましょう。各行の equals を equals に置き換えると、式はすぐに True と評価されます。

myAny even [1..]
foldr step False [1..]
step 1 (foldr step False [2..])
even 1 || (foldr step False [2..])
False  || (foldr step False [2..])
foldr step False [2..]
step 2 (foldr step False [3..])
even 2 || (foldr step False [3..])
True   || (foldr step false [3..])
True

これが機能するのはacc、 が評価されていないサンク (遅延評価) として渡されるためですが、関数の最初の引数||が正格であるためでもあります。

したがって、これは終了します：

True || and (repeat True)

しかし、これはしません:

and (repeat True) || True

|| の定義を見てください。これが当てはまる理由を確認するには：

True  || _ =  True
False || x =  x
于 2009-05-07T06:52:05.140 に答える
19

foldrについての私の理解は、リスト内のすべての項目をループすることです（そして、おそらくその理解は不完全です）。

foldr（とは異なりfoldl）は、リストのすべての項目をループする必要はありません。がどのようfoldrに定義されているかを確認することは有益です。

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

toの呼び出しfoldrが評価されると、関数への呼び出しの評価が強制されますf。ただし、への再帰呼び出しがfoldr関数の引数にどのように埋め込まれているかに注意してくださいf。f2番目の引数を評価しない場合、その再帰呼び出しは評価されません。

于 2009-05-07T07:40:01.157 に答える
1

ここで重要な点は、Haskell が厳密でない言語であるということです。「非厳密」とは、非厳密な関数を許可することを意味します。これは、関数パラメーターが使用される前に完全に評価されない可能性があることを意味します。これは明らかに、「結果が必要になるまで計算を遅らせる手法」である遅延評価を可能にします。

この Wiki 記事から始めます

于 2009-05-07T06:43:31.713 に答える
1

私はHaskellを知りませんが、あなたの場合、遅延評価のために機能すると思います。無限に長いリストを操作できるため、リストにアクセスすると、必要に応じて結果が計算されます。

http://en.wikipedia.org/wiki/Lazy_evaluationを参照

于 2009-05-07T06:44:09.950 に答える