7

ページFoldr Foldl Foldl'で について説明foldl'し、次のように定義しています。

foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x 
                    in seq z' $ foldl' f z' xs

これは、スペース リークを回避するために行われます。つまりfold'、一定のサイズの結果が一定のスペースのみを使用するようにします。

ただし、ここで指摘されているように、これは必ずしも機能するとは限りません。

関連seqする関数は、最上位のコンストラクターのみを評価します。アキュムレータがより複雑なオブジェクトである場合fold'でも、未評価のサンクが構築されます。

明らかな解決策は、次のように変更seqするdeepseqことです ( を使用していると仮定しますNFData)。

foldl_strict f z []     = z
foldl_strict f z (x:xs) = let z' = z `f` x 
                          in deepseq z' $ foldl_strict f z' xs

しかし、ループを通過するたびに構造全体をトラバースする必要があるため、これは非常に非効率的であると感じてdeepseqいます (コンパイラーがこれが不要であることを静的に証明できない限り)。

次に、これを試しました：

foldl_stricter  f z l      = deepseq z $ foldl_stricter' f z l
foldl_stricter' f z []     = z
foldl_stricter' f z (x:xs) = let z' = deepseq x $ z `f` x 
                             in seq z' $ foldl_stricter' f z' xs

しかし、この問題があることがわかりました。以下は、3 を返す必要がある場合に失敗します。

foldl_stricter (\x y -> x + head y) 0 [[1..],[2..]]

だからfold_stricter厳しすぎる。リストは厳密である必要はありません。スペースリークを防ぐために重要なことは、アキュムレータが厳密であることです。fold_stricter行き過ぎて、リストも厳密になり、上記が失敗します。

に戻りfold_strictます。deepseqサイズのデータ​​構造で繰り返し実行すると時間nがかかりますか、それとも初回とそれ以降の時間O(n)だけですか? （以下のコメントでdbaupが示唆しているように）O(n)O(1)

4

1 に答える 1

3

実際、 の 2 つの実装foldlは大きく異なります。答えを計算するためf z xに完全にトラバースする必要があるという保証はないので、不必要な作業を行う可能性があります。また、が完全に評価されたとしても、ネストされたサンクがないという保証はないため、十分に機能しない可能性があります。xdeepseq x (f z x)xf z xlet z' = deepseq x (f z x) in seq z' (foo z')

あなたが述べた問題の正しい解決策はfoldl'、厳密なデータ型をアキュムレータ型として使用することです。このように、seq構造体全体が完全に評価されたことを知るためにコンストラクターをチェックするだけでよく、逆にコンストラクターを強制すると、構造体全体が完全に評価されます。

于 2012-06-19T05:24:04.913 に答える