7

foldrリスト内包表記とのある種の融合を行うように思われるためfoldl、この例では (21mb)と比較してメモリ (11mb) の割り当てが少なくて済みます。

myfunc = sum $ foldr g acc [ f x | x <- xs ]
f x = ..
g x y = ..

誰かがその方法と理由を説明できますか? また、遅延評価がこれにどのように役立つか。

4

3 に答える 3

8

本質的に、 として理解を脱糖することができmap f xsます。これをコンパイルしている場合、ghc は確かに合計、折り畳み、およびマップを単一のパスに融合できるはずです: http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion. しかし、そうでない場合でも、怠惰はメモリ使用量の友です。マップによって生成されるリストは遅延型です。f は要求された場合にのみ適用されます。f は、foldr が要求した場合にのみ要求されます。そして、あなたのフォルダーは明らかに別の（怠惰な）リストを生成しているため、フォールドの各ステップは合計によってのみ要求されます。したがって、各関数は順番に適用されますが、完全な中間データ構造を一度に生成する必要はありません。関数構成の完全なセットを作成した場合、評価モデルは、この特定のコード セットを処理する傾向があり、一連の手を振ってモジュロし、幾分ループのようになります (ただし、融合がなければ、かなりの量のループを使用します)。間接の）。

于 2011-12-09T17:19:59.477 に答える
8

左折りは、リスト全体をトラバースする前に出力 (結果の一部) を生成することはできません。フォールドする関数によっては、大量のメモリを使用する大きなデータ構造または大きなサンクが構築される可能性があります (たとえば (+) を のリストにフォールドすると、定数メモリで実行できますInt)。

適切な関数 (2 番目の引数を検査せずに [部分的な] 結果を生成できるような) の場合、右折畳みはその結果をインクリメンタルに生成できるため、結果が適切に消費され、入力リストが適切に生成された場合、計算全体を実行できます。小さな一定のスペースで。sclvが言ったように、それらの場合、基本的にループになります。

于 2011-12-09T17:24:43.310 に答える
1

これは GHC コンパイラの機能です。while基本的に、GHC はいつリストが「パイプライン」で使用されているかを認識することができ、構造全体を、リストをまったく割り当てない C の -loop に相当するものに変換できます。

これが機能する理由と機能しfoldrない理由は、例で使用しfoldlている関数によって異なりgます。foldrは とは対照的に、パラメータとして指定された関数の結果foldlを蓄積するため(別名:実際に関数の評価を開始する前にリスト全体が必要になるため、未評価の関数と最終要素の巨大な「サンク」が構築されます。その結果としてのリスト - この場合、非常に多くのメモリを使用するのはそのためです -リスト入力を取得するとすぐに評価を開始できます)、アキュムレータでは「厳密」と呼ばれ、特定の仮定は最適化につながる可能性のあるコンパイラ。foldlgfoldrg

たとえば、関数gがリストである値を生成する場合、前述の「パイプライン」最適化戦略を継続し、基本的にfoldrを a のように扱い、map構成全体 (リストの生成からリストの消費まで) を厳密なループにします。これが可能なのはfoldr、 が消費するすべてのリスト要素に対して正確に 1 つのリスト要素を生成するためです。これfoldlは保証されていません (特に無限リストの場合)。

于 2011-12-09T17:23:26.943 に答える