131

この質問の 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

ただし、これは関数の動作方法ではありません。これはどのように間違っていますか？

4

4 に答える 4

248

sfoldの違いはしばしば混乱の原因と思われるため、より一般的な概要を以下に示します。

[x1, x2, x3, x4 ... xn ]関数fとシードを使用してn 値のリストを折り畳むことを検討してくださいz。

foldlは：

  • 左連想:f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Tail recursive : リストを繰り返し処理し、後で値を生成します
  • Lazy : 結果が必要になるまで何も評価されない
  • Backwards :foldl (flip (:)) []リストを反転します。

foldrは：

  • 右結合:f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
  • 引数への再帰: 各反復はf、次の値とリストの残りを折りたたんだ結果に適用されます。
  • Lazy : 結果が必要になるまで何も評価されない
  • Forwards :foldr (:) []変更されていないリストを返します。

foldlここで、時々人をつまずかせる微妙なポイントがfあります。また、lazyであるため、結果が必要になるまで何も評価されません。これは、結果の任意の部分を計算するために、Haskell が最初にネストされた関数アプリケーションの式を構築するリスト全体を反復し、次に最も外側の関数を評価し、必要に応じてその引数を評価することを意味します。常に最初の引数を使用する場合、これは Haskell が最も内側の項まで再帰しなければならないことを意味します。ff

これは明らかに、ほとんどの関数型プログラマーが知っていて愛用している効率的な末尾再帰とはかけ離れています!

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

一方、 を検討してfoldrください。これも怠け者ですが、forwardsを実行するため、結果の内側に の各アプリケーションfが追加されます。したがって、結果を計算するために、Haskell は単一の関数アプリケーションを作成します。その 2 番目の引数は、折り畳まれたリストの残りです。2 番目の引数 (データ コンストラクターなど) が lazy である場合、結果は段階的にlazyになり、折り畳みの各ステップは、それを必要とする結果の一部が評価されたときにのみ計算されます。f

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

したがって、注意すべき重要な点は次の 2 つです。

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

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

しかし、大きな (ただし無限ではない) リストを折りたたむことによって、遅延のない結果を生成したい場合はどうすればよいでしょうか? このために、標準ライブラリが思慮深く提供するstrict foldが必要です。

foldl'は：

  • 左連想:f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
  • Tail recursive : リストを繰り返し処理し、後で値を生成します
  • Strict : 各関数適用は途中で評価されます
  • Backwards :foldl' (flip (:)) []リストを反転します。

foldl'はstrictであるため、結果を計算するために Haskell は各ステップで評価 fを行います。左の引数に未評価の巨大な式を蓄積させるのではありません。これにより、必要な通常の効率的な末尾再帰が得られます。言い換えると：

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

Haskell wiki にも、これについて議論しているページがあります。

于 2010-06-21T14:30:35.507 に答える
28 
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は、常に「外側」または「左側」にあるため、最初に展開されます。無限に。

于 2010-06-21T05:54:41.283 に答える
11

Haskell のドキュメントhereで、foldl が末尾再帰的であり、値を返す前に次のパラメーターで自分自身を呼び出すため、無限リストが渡された場合に終了しないことがわかります...

于 2010-06-21T05:38:42.330 に答える
0

Haskell はわかりませんが、Scheme ではfold-right常にリストの最後の要素を最初に「処理」します。したがって、循環リスト (無限リストと同じ) では機能しません。

fold-right末尾再帰的に記述できる かどうかはわかりませんが、循環リストではスタック オーバーフローが発生するはずです。fold-leftOTOH は通常末尾再帰で実装され、早期に終了しないと無限ループに陥ります。

于 2010-06-21T05:40:13.760 に答える