私はfoldlとfoldrをテストしたかった。私が見てきたことから、末尾再帰の最適化のために、可能な限りfoldrよりもfoldlを使用する必要があります。
意味あり。ただし、このテストを実行した後、私は混乱しています：
folderr (time コマンドを使用する場合は 0.057 秒かかります):
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
foldl (time コマンドを使用すると 0.089 秒かかります):
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
この例が些細なことであることは明らかですが、foldr が foldl を上回っている理由については混乱しています。これは、foldl が勝つ明確なケースではないでしょうか?
遅延評価の世界へようこそ。
厳密な評価の観点から考えると、foldl は末尾再帰であるため、foldl は「良い」ように見え、foldr は「悪い」ように見えますが、最初に最後の項目を処理できるように、foldr はスタックにタワーを構築する必要があります。
しかし、遅延評価は形勢を逆転させます。たとえば、map 関数の定義を見てみましょう。
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Haskell が厳密な評価を使用する場合、これはあまり良くありません。最初にテールを計算してから、項目を先頭に追加する必要があるためです (リスト内のすべての項目に対して)。それを効率的に行う唯一の方法は、要素を逆に構築することだと思われます。
しかし、Haskell の遅延評価のおかげで、この map 関数は実際には効率的です。Haskell のリストはジェネレーターと考えることができ、この map 関数は、入力リストの最初の項目に f を適用することによって最初の項目を生成します。2 番目のアイテムが必要な場合は、(余分なスペースを使用せずに) 同じことを繰り返します。
mapは次のように記述できることがわかりますfoldr。
map f xs = foldr (\x ys -> f x : ys) [] xs
見ただけではわかりにくいですが、foldr はf最初の引数をすぐに与えることができるため、遅延評価が開始されます。
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
fdefined bymapは最初のパラメーターのみを使用して結果リストの最初の項目を返すことができるため、折り畳みは定数空間で遅延して動作できます。
さて、遅延評価は逆効果です。たとえば、sum [1..1000000] を実行してみてください。スタック オーバーフローが発生します。なぜそれが必要なのですか？左から右に評価するだけですよね？
Haskell がそれを評価する方法を見てみましょう。
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
sum = foldl (+) 0
sum [1..1000000] = foldl (+) 0 [1..1000000]
= foldl (+) ((+) 0 1) [2..1000000]
= foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
= foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
...
= (+) ((+) ((+) (...) 999999) 1000000)
Haskell は怠惰すぎて、追加をそのまま実行できません。代わりに、数値を取得するために強制する必要がある評価されていないサンクの塔になってしまいます。すべてのサンクを評価するために深く再帰する必要があるため、この評価中にスタック オーバーフローが発生します。
幸いなことに、Data.List には、foldl'厳密に動作する特別な関数が呼び出されています。 foldl' (+) 0 [1..1000000]スタックオーバーフローしません。（注：テストでに置き換えfoldlてみましfoldl'たが、実際には実行が遅くなりました。）
編集：この問題をもう一度見てみると、現在の説明はすべてやや不十分だと思うので、もっと長い説明を書きました。
違いは、それらの削減機能をどのようfoldlに適用するかです。ケースfoldrを見ると、次のように拡張できますfoldr
foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...
このリストはによって処理されsum、次のように消費されます。
sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...
リスト連結の詳細は省略しましたが、これが削減の進め方です。重要な部分は、リストの走査を最小限に抑えるためにすべてが処理されることです。リストを1回トラバースするfoldrだけで、連結は連続的なリストトラバーサルを必要とせず、sum最終的に1回のパスでリストを消費します。重要なのは、リストの先頭がfoldrすぐにからに利用できるsumため、すぐにsum作業を開始でき、値が生成されるときに値をgcすることができるということです。のような融合フレームワークを使用vectorすると、中間リストでさえも融合される可能性があります。
これをfoldl関数と比較してください。
b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...
リストの先頭は、終了するまで使用できないことに注意してくださいfoldl。sumこれは、作業を開始する前に、リスト全体をメモリ内に構築する必要があることを意味します。これは全体的にはるかに効率的ではありません。2つのバージョンをで実行すると+RTS -s、foldlバージョンからの悲惨なガベージコレクションのパフォーマンスが示されます。
これは、役に立たない場合でもありfoldl'ます。の追加された厳密さはfoldl'、中間リストの作成方法を変更しません。リストの先頭はfoldl'が終了するまで使用できないため、結果は。よりも遅くなりますfoldr。
私は次のルールを使用して、fold
foldl'（たとえば、これが唯一の/最後のトラバーサルになります）foldr。foldl。foldrリストの遅延評価にはトラバーサル方向が最適であるため、ほとんどの場合、これが最良のフォールド関数です。また、無限のリストを処理できるのはこれだけです。の余分な厳密さによりfoldl'、場合によっては高速化できますが、これは、その構造をどのように使用するか、およびそれがどれほど怠惰であるかに依存します。
私が何かを見逃していない限り、まだ誰も実際にこれについて本当の答えを言っていないと思います（これは真実であり、反対票で歓迎されるかもしれません）。
foldrこの場合の最大の違いは、次のようにリストを作成することだと思います。
[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))
一方foldl、次のようにリストを作成します。
((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]
foldr微妙な違いですが、このバージョン++では、左の引数としてリスト要素が常に 1 つしかないことに注意してください。バージョンでは、の左引数foldlには最大 999999 個の要素++(平均で約 500000) がありますが、右引数には 1 つの要素しかありません。
ただし、++左引数リスト全体を最後まで調べてから、その最後の要素を右引数の最初の要素に再ポイントする必要があるため、左引数のサイズに比例して時間がかかります (せいぜい、実際にはコピーしてください）。右側の引数リストは変更されていないため、それがどれだけ大きくても問題ありません。
そのため、foldlバージョンが大幅に遅くなります。私の意見では、怠惰とは何の関係もありません。
問題は、末尾再帰の最適化がメモリの最適化であり、実行時間の最適化ではないことです。
末尾再帰の最適化により、再帰呼び出しごとに値を覚えておく必要がなくなります。
したがって、foldlは実際には「良い」であり、foldrは「悪い」です。
たとえば、foldrとfoldlの定義を考えてみましょう。
foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs
foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)
これが、「foldl（+）0[1,2,3]」という式の評価方法です。
foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6
foldlは値0、1、2 ...を記憶していませんが、式全体（（（0 + 1）+2）+3）を引数として怠惰に渡し、最後の評価まで評価しないことに注意してください。 foldlは、基本ケースに到達し、まだ評価されていない2番目のパラメーター（z）として渡された値を返します。
一方、フォルダは次のように機能します。
foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6
ここでの重要な違いは、foldlが最後の呼び出しで式全体を評価し、記憶された値に到達するために戻る必要がないことです。foldrは、呼び出しごとに1つの整数を記憶し、呼び出しごとに加算を実行します。
foldrとfoldlは必ずしも同等ではないことを覚えておくことが重要です。たとえば、この式を抱擁で計算してみてください。
foldr (&&) True (False:(repeat True))
foldl (&&) True (False:(repeat True))
foldrとfoldlは、ここで説明する特定の条件下でのみ同等です。
（私の悪い英語でごめんなさい）
a の場合、[0.. 100000]foldr が最後の要素から開始できるように、リストをすぐに展開する必要があります。次に、物事をまとめると、中間結果は次のようになります
[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list
このリストの値を変更することは誰にも許可されていないため (Haskell は純粋な関数型言語です)、コンパイラは値を自由に再利用できます。中間値は、個別のリストではなく[99999, 100000]、展開されたリストへの単純なポインターにすることもできます。[0.. 100000]
b については、中間値を見てください。
[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]
リストの最後を変更すると、それを指す他の値が変更されるため、これらの中間リストはそれぞれ再利用できません。そのため、メモリ内に構築するのに時間がかかる余分なリストを作成しています。したがって、この場合、中間値であるこれらのリストの割り当てと入力により多くの時間を費やします。
リストのコピーを作成しているだけなので、完全なリストを展開することから始めて、リストの後ろから前にポインターを移動し続けるため、 a の方が高速に実行されます。
テールも最適化されていませfoldlん。foldrのみfoldl'です。
しかし、あなたの場合、++withを使用するfoldl'ことはお勧めできません。なぜなら、 を連続して評価++すると、成長するアキュムレータを何度もトラバースするからです。
さて、違いが明らかなように関数を書き直しましょう-
a :: a -> [a] -> [a]
a = (:)
b :: [b] -> b -> [b]
b = flip (:)
b は a よりも複雑であることがわかります。正確にしたい場合はa、値を計算するために1つの削減ステップがb必要ですが、2つ必要です。これにより、測定している時間差が生じます。2 番目の例では、2 倍の削減を実行する必要があります。
//編集: しかし、時間の複雑さは同じなので、あまり気にしません。