haskell - Haskell サンク - foldl と foldr

Question

foldlHaskell を学んでいると、がサンクを作成してスタックをクラッシュさせる可能性があるという事実に出くわしたので、 foldl'fromを使用することをお勧めしますData.List。foldlたとえば、ではなく、単に である理由は何foldrですか?

ありがとう

Answer 1

foldr'自分で効果を出せるので必要ありません。

理由は次のとおりfoldl f 0 [1,2,3]です。これは に展開されるf (f (f 0 1) 2) 3ため、何かを元に戻すまでに、thunks を作成する必要が(f 0 1)あり(f (f 0 1) 2)ます。これを回避したい場合 (続行する前にこれらの部分式を評価することによって)、foldlそれを行うように指示する必要がありfoldl'ます。

ではfoldr、事情が異なります。返されるのfoldr f 0 [1, 2, 3]はf 1 (foldr f 0 [2, 3])(括弧内の式がサンクの場合) です。の外側のアプリケーション (の一部) を評価したい場合はf、線形数のサンクを最初に作成しなくてもすぐに実行できます。

しかし、一般的には、2 番目の引数を見る前に既に何かを実行できる (たとえば、リスト コンストラクターを生成する)foldrための遅延関数を使用しています。f

foldrstrict で使用するとf(例: (+))、リストの最後に到達するまですべてのアプリケーションがスタックに置かれるという望ましくない効果があります。明らかにあなたが望むものではなく、見た目foldr'が助けになる状況ではありません。