foldl with（++）はfoldrよりもかなり遅い

Question

foldlがfoldrよりも遅いのはなぜですか？ は、私はそれが正常に動作します（時間計算量はO（N）である）「」

a = [[1],[2],[3]] 

のようなリストのリストを持っていると

foldr (++) [] a 

倍使用して、リストにそれを変更したいです。しかし、代わりにfoldlを使用すると、時間が非常に遅くなります（時間の複雑さはO（n^2）です）。

foldl (++) [] a 

foldlのちょうど左側から入力リスト折りたたみされた場合、

(([] ++ [1]) ++ [2]) ++ [3] 

とfoldr右側からのものである、

[1] ++ ([2] ++ ([3] ++ [])) 

計算の数（++）どちらの場合も同じであるはずです。なぜfoldrはとても遅いのですか？時間の複雑さに応じて、foldlはfoldrと同じ回数だけ入力リストをスキャンするように見えます。私はコンピュータに次の時間を使っていました。

length $ fold (++) [] $ map (:[]) [1..N] (fold is either foldl or foldr) 

Answer 1

これはなんで++の仕事です。これは、最初の引数で誘導によって定義されていることに注意してください。

[]  ++ ys = ys 
(x:xs) ++ ys = x : (xs ++ ys) 

再帰呼び出しの回数は、length xsに依存します。

このため、xs ++ ysでは、小文字のxsと大文字のysを使用する方が便利です。

[1] ++ ([2] ++ ([3] ++ ... 

我々は唯一の倍のコストがO（n）を作り、++の左側に短い（O（1）-length）のリストを持っている：右に折ることは、これを達成することを

注意。代わりに、左側に折りたたみ

が悪い：

((([] ++ [1]) ++ [2]) ++ [3]) ++ ... 

左引数がますます大きくなります。したがって、ここではO（n^2）の複雑さが得られます。

この引数は、出力リストの要求方法を考慮して、より正確にすることができます。 foldrはその結果を「ストリーミング」方式で生成することがわかります。最初の出力リストセルは入力のほんの一部を強制します - 最初の++だけを実行する必要があり、最初の再帰的ステップだけが実際に必要です。代わりにfoldlの結果の最初の項目だけを要求すると、すべて++コールが強制され、非常に高価になります（各コールには再帰的ステップが1つのみ必要ですが、O（n）コールがあります）。