遅延評価の世界へようこそ。
厳密な評価の観点から考えると、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)
f
defined 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'
たが、実際には実行が遅くなりました。)