foldl と foldr をテストしたかったのです。私が見た限りでは、末尾再帰の最適化のため、できる限り foldl を foldr よりも使用すべきです。
これは理にかなっています。しかし、このテストを実行した後、私は混乱しました。
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 が勝つ明らかなケースではないでしょうか?
ベストアンサー1
遅延評価の世界へようこそ。
厳密な評価の観点から考えると、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 番目の項目が必要な場合は、同じことをもう一度行います (余分なスペースは使用しません)。
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 by はmap最初のパラメータのみを使用して結果リストの最初の項目を返すことができるため、 fold は定数スペースで遅延して動作できます。
さて、遅延評価は確かに逆効果です。たとえば、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'が、実際には実行速度が低下しました。)