[解決済み] foldlは末尾再帰的なのに、なぜfoldrはfoldlより高速に動作するのか？

質問

私はfoldlとfoldrを比較テストしたいと思いました。私が見たところでは、末尾再帰最適化のために、できる限りfoldrよりもfoldlを使用するべきです。

これは理にかなっています。しかし、このテストを実行した後、私は混乱しています。

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が勝つ明確なケースであるべきではないでしょうか？

どのように解決するのですか？

怠惰な評価の世界へようこそ。

厳密な評価という観点で考えると、foldlは末尾再帰的なので、foldlは"good"、foldrは"bad"に見えますが、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)

なぜなら f で定義される 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' を追加しましたが、実際には実行速度が遅くなりました)。