foldlは末尾再帰ですが、なぜfoldrがfoldlよりも高速に実行されるのでしょうか。

2010年08月07日に質問されました。  ·  閲覧回数 17.9k回  ·  ソース

Ori picture
2010年08月07日

foldlとfoldrをテストしたかった。 私が見たところ、テール再帰の最適化のために、できる限りfoldl overfoldrを使用する必要があります。

意味あり。 ただし、このテストを実行した後、私は混乱しています。

foldr(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が勝つ明確なケースではないでしょうか?

回答

Joey Adams picture
2010年08月07日
106

遅延評価の世界へようこそ。

厳密な評価の観点から考えると、foldlは末尾再帰であるため、foldlは「良好」に見え、foldrは「不良」に見えますが、foldrはスタック内にタワーを構築して、最後のアイテムを最初に処理できるようにする必要があります。

ただし、遅延評価はテーブルを変えます。 たとえば、map関数の定義を考えてみましょう。

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Haskellが厳密な評価を使用した場合、これはあまり良くありません。最初にテールを計算してから、アイテムの前に(リスト内のすべてのアイテムに対して)追加する必要があるためです。 それを効率的に行う唯一の方法は、要素を逆に構築することだと思われます。

ただし、Haskellの遅延評価のおかげで、このマップ関数は実際には効率的です。 Haskellのリストはジェネレーターと考えることができ、このマップ関数は入力リストの最初の項目にfを適用することによって最初の項目を生成します。 2番目のアイテムが必要な場合は、同じことを再度実行します(余分なスペースを使用しません)。

mapfoldr観点から説明できることがわかりました:

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)

f定義されたmapは、最初のパラメーターのみを使用して結果リストの最初の項目を返すことができるため、フォールドは一定のスペースで遅延操作できます。

さて、遅延評価は後戻りします。 たとえば、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]はスタックオーバーフローしません。 (注:テストでfoldlfoldl'に置き換えようとしましたが、実際には実行速度が低下しました。)

John L picture
2010年08月07日
27

編集:この問題をもう一度見てみると、現在の説明はすべてやや不十分だと思うので、もっと長い説明を書きました。

違いは、 foldlfoldrが削減機能を適用する方法にあります。 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])
...

リストの連結の詳細は省略しましたが、これが削減の進行方法です。 重要な部分は、リストの走査を最小限に抑えるためにすべてが処理されることです。 foldrはリストを1回だけトラバースし、連結は継続的なリストトラバースを必要とせず、 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が機能し始める前に、リスト全体をメモリ内に構築する必要があることを意味します。 これは全体的にはるかに効率的ではありません。 +RTS -sを使用して2つのバージョンを実行すると、foldlバージョンからの惨めなガベージコレクションのパフォーマンスが示されます。

これは、 foldl'が役に立たない場合でもあります。 追加されたfoldl'厳密さは、中間リストの作成方法を変更しません。 リストの先頭はfoldl 'が終了するまで使用できないため、結果はfoldrよりも遅くなります。

次のルールを使用して、 fold最適な選択を決定します

  • 縮小されたフォールドの場合は、 foldl'使用します(たとえば、これが唯一の/最後のトラバーサルになります)
  • それ以外の場合はfoldrます。
  • foldlは使用しないでください。

リストの遅延評価にはトラバーサル方向が最適であるため、ほとんどの場合、 foldrが最適なフォールド関数です。 また、無限のリストを処理できるのはこれだけです。 foldl'の余分な厳密さにより、場合によっては高速化できますが、これは、その構造をどのように使用するか、およびそれがどれほど怠惰であるかによって異なります。

Clinton picture
2013年03月14日
9

私が何かを見逃していない限り、誰もこれについて実際に本当の答えを言ったとは思いません(これは真実であり、反対票で歓迎されるかもしれません)。

この場合の最大の違いは、 foldrようにリストを作成することだと思います。

[0] ++([1] ++([2] ++(... ++ [1000000])))

foldlは、次のようにリストを作成します。

((([0] ++ [1])++ [2])++ ...)++ [999888])++ [999999])++ [1000000]

微妙な違いがありますが、 foldrバージョンでは、 ++左側の引数として常に1つのリスト要素しかないことに注意してください。 foldlバージョンでは、 ++の左側の引数には最大999999個の要素がありますが(平均で約500000)、右側の引数には1つの要素しかありません。

ただし、 ++は、左の引数リスト全体を最後まで調べてから、その最後の要素を右の引数の最初の要素に再ポイントする必要があるため、左の引数のサイズに比例して時間がかかります(せいぜい、おそらく実際にコピーを行う必要があります)。 正しい引数リストは変更されていないため、サイズは関係ありません。

そのため、 foldlバージョンははるかに低速です。 私の意見では、怠惰とは何の関係もありません。

matiascelasco picture
2013年02月17日
7

問題は、末尾再帰の最適化がメモリの最適化であり、実行時間の最適化ではないことです。

末尾再帰の最適化により、再帰呼び出しごとに値を記憶する必要がなくなります。

したがって、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は、ここで説明です。

(私の悪い英語でごめんなさい)

Harold L picture
2010年08月07日
2

aの場合、フォルダが最後の要素から開始できるように、 [0.. 100000]リストをすぐに展開する必要があります。 次に、物事を折りたたむと、中間結果は次のようになります。

[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]

リストの末尾を変更すると、それを指す他の値も変更されるため、これらの中間リストはそれぞれ再利用できません。 つまり、メモリに組み込むのに時間がかかる追加のリストをたくさん作成していることになります。 したがって、この場合、中間値であるこれらのリストの割り当てと入力に多くの時間を費やします。

リストのコピーを作成しているだけなので、リスト全体を展開することから始めて、リストの後ろから前にポインタを移動し続けるため、実行速度が速くなります。

Hynek -Pichi- Vychodil picture
2010年08月07日
1

foldlfoldrもテール最適化されていません。 たったのfoldl'です。

しかし、あなたの場合、 ++foldl'と一緒に使用することは、 ++を連続して評価すると、成長するアキュムレータを何度もトラバースするため、お勧めできません。

Martin Jonáš picture
2010年08月07日
-3

さて、違いが明白になるように関数を書き直しましょう-

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

bはaよりも複雑であることがわかります。 正確にしたい場合、 aは値を計算するために1つの削減ステップが必要ですが、 bは2つ必要です。 これにより、測定する時間差が生じます。2番目の例では、2倍の削減を実行する必要があります。

//編集:しかし、時間の複雑さは同じなので、あまり気にしません。