無限のリストを使用したfoldlとfoldrの動作

Question

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

ただし、これは関数の動作ではありません。どうやって間違っているの？

Answer 1

どのように folds異なることは頻繁に混乱の原因であるように思われるので、より一般的な概要を次に示します。

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. 。それも怠zyですが、それが実行されるためです フォワード, 、の各アプリケーション f に追加されます 中身 結果の。したがって、結果を計算するために、Haskellは 独身 関数アプリケーション、その2番目の引数は、折り畳まれたリストの残りの部分です。もしも f その2番目の引数では怠zyです - たとえば、データコンストラクター - 結果は 徐々に怠zy, 、折り畳みの各ステップで、それが必要な結果の一部が評価された場合にのみ計算されます。

だから私たちはその理由を見ることができます foldr 時々、無限のリストで動作するとき foldl そうではありません：前者は無限のリストを別の怠zyな無限データ構造にゆっくりと変換することができますが、後者は結果の任意の部分を生成するためにリスト全体を検査する必要があります。一方で、 foldr すぐに両方の引数を必要とする関数で、 (+), 、作品（またはむしろ、機能しません）のように foldl, 、評価する前に大きな表現を構築します。

したがって、注意すべき2つの重要なポイントは次のとおりです。

• foldr ある怠zyな再帰データ構造を別のものに変換できます。
• それ以外の場合、怠zyなfoldは、大型または無限のリストにスタックオーバーフローでクラッシュします。

あなたはそれがそのように聞こえることに気づいたかもしれません foldr すべてを行うことができます foldl さらに、さらに。これは本当です！実際には、 foldlはほとんど役に立たない！

しかし、大きな（ただし無限ではない）リストを折り畳んで怠zyな結果を生み出したい場合はどうでしょうか？このために、私たちはaが欲しい 厳格な折りたたみ, 、 どれの しかし、標準的なライブラリが提供しています:

foldl' は：

• 左連想: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• 尾の再帰: ：それはリストを繰り返し、その後価値を生み出します
• 厳しい: ：各関数アプリケーションは、途中で評価されます
• 後方: foldl' (flip (:)) [] リストを逆にします。

なぜなら foldl' は 厳しい, 、結果を計算するには、Haskellが意志します 評価 f 各ステップで、左の議論に膨大な、平らでない表現を蓄積させる代わりに。これにより、通常の効率的な尾の再帰が私たちに与えてくれます！言い換えると：

• foldl' 大きなリストを効率的に折り畳むことができます。
• foldl' 無限のリストに無限のループ（スタックオーバーフローを引き起こさない）に吊るします。

Haskell Wikiにはあります これについて議論するページ, 、 同じように。

Answer 2

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

等

直感的に、 foldl 常に「屋外」または「左」にあるので、最初に拡張されます。広告infinitum。

Answer 3

Haskellのドキュメントで見ることができます ここ そのfoldlは尾を回収するものであり、値を返す前に次のパラメーターでそれ自体を呼び出すため、無限のリストを渡すと終了することはありません...

Answer 4

私はハスケルを知りませんが、スキームでは、 fold-right 最初にリストの最後の要素に常に「行動」します。したがって、循環リストでは機能しません（これは無限のリストと同じです）。

かどうかはわかりません fold-right 尾を回復的に書くことはできますが、サイクリックリストではスタックオーバーフローを取得する必要があります。 fold-left OTOHは通常、テール再帰で実装されており、早期に終了しない場合、無限のループで立ち往生します。