[解決済み] 無限リストでのfoldlとfoldrの動作

質問

のmyAny関数のコードは この質問 のコードはfoldrを使用しています。 これは、述語が満たされたときに無限リストの処理を停止します。

foldlを使って書き直しました。

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

(ステップ関数の引数が正しく逆になっていることに注意してください)

ただし、無限リストの処理を停止することはなくなりました。

のように関数の実行をトレースしようとしました。 Apocalispの回答 :

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

しかし、これはこの関数の動作とは異なります。 どのように間違っているのでしょうか？

どのように解決するのですか？

どのように fold がどのように異なるかは、しばしば混乱の原因となっているようなので、ここではより一般的な概要を説明します。

n 個の値からなるリストを折りたたむことを考えます [x1, x2, x3, x4 ... xn ] をある関数で f とシード z .

foldl は

• 左連想 : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• テールリカーシブ : リストを繰り返し、その後に値を生成します。
• 怠惰な : 結果が必要になるまで何も評価されない
• 後方 : foldl (flip (:)) [] はリストを反転させる。

foldr です。

• 右連想 : f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• 引数への再帰的 : 各反復が適用される f を次の値に、そしてリストの残りの部分を折りたたんだ結果に適用します。
• 怠惰な : 結果が必要になるまで何も評価されない
• フォワード : foldr (:) [] はリストを変更せずに返す。

ここには、時々人をつまずかせる少し微妙な点があります。なぜなら foldl は 後ろ向き の各アプリケーションは f に追加されます。 の外側 であるため 怠け者 であるため、結果が必要とされるまで何も評価されません。これは、結果のどの部分を計算するにしても、Haskellは最初に リスト全体 を繰り返し、ネストされた関数アプリケーションの式を構築し、次に 一番外側の 関数を評価し、必要に応じてその引数を評価します。もし f が常に最初の引数を使用する場合、Haskell は最内部の項まで再帰的に計算し、そこから逆算して f .

これは明らかに、多くの関数型プログラマが知っている効率的な末尾再帰とはかけ離れたものです!

実際、たとえ foldl は技術的に末尾再帰的ですが、これは結果式全体が何かを評価する前に構築されるからです。 foldl はスタックオーバーフローを引き起こす可能性があります!

一方 foldr . これも怠慢ですが、これは フォワード を実行するため、それぞれのアプリケーションは f に追加されます。 の内側 の中に追加されます。つまり、結果を計算するために、Haskellは シングル 関数アプリケーションを構築し、その第2引数に折りたたまれたリストの残りを渡します。もし f がその第二引数で遅延している場合、例えばデータコンストラクタの場合、その結果は 漸進的な遅延 であり、折り返しの各ステップは、それを必要とする結果の一部が評価されたときにのみ計算されます。

ということは、なぜ foldr が無限リストで動作することがあるのは foldl は動作しないことがあります。前者は無限リストを遅延無限データ構造に変換することができますが、後者は結果の一部を生成するためにリスト全体を検査しなければなりません。一方 foldr のように、両方の引数をすぐに必要とする関数で (+) のような、すぐに両方の引数を必要とする関数では、ほとんど foldl のように、評価する前に巨大な式を構築します。

というわけで、重要なポイントはこの2つです。

• foldr は、ある遅延再帰的なデータ構造を別のものに変換することができます。
• そうでなければ、遅延フォールドは大きなリストや無限リストでスタックオーバーフローでクラッシュします。

のように聞こえることにお気づきでしょうか？ foldr は何でもできる foldl ができること、さらにそれ以上のことができます。これは本当です! 実際 foldlはほとんど役に立たないのです!

しかし、大きな（しかし無限ではない）リストを折り返して、遅延のない結果を出したいとしたらどうでしょうか。このために、私たちは 厳密な折りたたみ で、これは は、標準ライブラリが意図的に提供する :

foldl' です。

• 左連想 : f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• テールリカーシブ : リストを繰り返し、その後に値を生成します。
• 厳密な : 各関数のアプリケーションは途中で評価される
• 後方 : foldl' (flip (:)) [] はリストを反転させる。

なぜなら foldl' は 厳しい を計算するために、Haskell は を評価します。 f を各ステップで評価し、左の引数が評価されない巨大な式を蓄積するのを防ぎます。これにより、私たちが望む、通常の効率的な末尾再帰が実現します 言い換えれば

• foldl' は大きなリストを効率的に折りたたむことができます。
• foldl' は無限リストに対して無限ループでハングアップします (スタックオーバーフローは起こりません)。

Haskellのwikiには というページがあります。 があり、同様に