haskell - なぜ `foldl1` はメモリ不足になるのに `foldr1` は問題なく動作するのですか?

Question

と を使ってlast関数を書きました。foldl1foldr1

lastr :: [a] -> a
lastr = foldr1 (flip const)

lastl :: [a] -> a
lastl = foldl1 (flip const)

短いリストでは問題なく機能します。しかし、非常に長いリスト [1..10^8] を試してみたところ、lastr は 6.94 秒でソリューションを返しましたが、lastl はメモリを使い果たしました。

foldr1 と foldl1 の定義は（私の理解では）

foldr1 f [x] = x
foldr1 f (x:xs) = f x $ foldr1 f xs

と

foldl1 f [x] = x
foldl1 f (x:y:ys)=foldl1 f $ f x y : ys

これらから見ると、foldl1 は次のような式を保持する必要があるため、foldl1 は foldr1 よりも少ないメモリを使用しているようf x1 $ f x2 $ f x3 $ f x4 $...に見えますf x y。

私の議論のどこが間違っているのか誰か教えてもらえますか?

Answer 1