なぜ `foldl1`がメモリ不足になるのですか？ 'foldr1`はうまく動作しますか？

Question

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

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

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

短いリストでも問題ありません。しかし、非常に長いリスト[1..10^8]で試してみると、lastrは6.94秒で解を返しますが、最後はメモリ不足です。

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はfoldr1は次のように表現を維持する必要があるためfoldr1より少ないメモリを使用しているようですf x1 $ f x2 $ f x3 $ f x4 $... foldl1は毎回f x yを計算し、10^8になるまでそれを保持するのではなく、リストの先頭要素として保存することができます。

誰かが私の議論に間違っていることを教えてもらえますか？

Answer 1

結合機能が第2引数で遅延している場合、右折はすぐに生成を開始できます。単純な例：

foldr1 (++) ["one", "two", "three", ...] 
    ~> "one" ++ foldr1 (++) ["two", "three", ...] 

、結果の最初の部分は、さらに(++)の第2引数を評価せずにすぐにアクセス可能です。これは、最初の部分が消費されたときにのみ評価する必要があります。多くの場合、最初の部分はすでにガベージコレクションされています。

結合関数としてf = flip constの例では、2番目の引数に厳密な^（1）の厳密な条件がありますが、全く評価する必要はありません。それは最初のものを無視します。それは右の折り畳みにも適しています。ここでは、

foldr1 f [x1, x2, x3, ... ] 
    ~> f x1 (foldr1 f [x2, x3, ... ]) 

を行くと、今最も外側fはすぐ

~> foldr1 f [x2, x3, ... ] 
    ~> f x2 (foldr1 f [x3, ... ]) 
    ~> foldr1 f [x3, ... ] 

と各ステップで評価することができ、最も外側のfは常にすぐに（完全に）評価することができ、かつ1つのリスト要素は捨て。

リストは順次消費時に一定の間隔でそれを作成することができる発電機により与えられた場合、

last = foldr1 (flip const) 

は、一定の間隔で実行することができます。

左の折り目では、物が異なります。それはテール再帰的なので、

foldl1 f (x:y:zs) = foldl f x (y:zs) = foldl f (f x y) zs 

リストが終わるまで何も返すことができません。特に、左折は決して無限のリストで終了することはできません。

は今、私たちの場合f = flip constを見て、我々はすぐにx2にf x1 x2を評価することが可能となり、その後、f x2 x3 = x3が、それは、この特別なfのためにのみ可能であるだろう。もちろん、

foldl1 f [x1, x2, x3, x4, ...] 
    ~> foldl f x1 [x2, x3, x4, ... ] 
    ~> foldl f (f x1 x2) [x3, x4, ... ] 
    ~> foldl f (f (f x1 x2) x3) [x4, ... ] 

を見つけます。

foldlは一般的な高次関数なので、中間結果が決して必要とされない可能性があるため、中間結果を評価することはできません。実際にはここでは必要ありません。リストは、1式

f (f (f (f ...y3) y2) y1) y0 
    ~> y0 

を取得し、最も外側のfは、最初の引数を構築するネストされたf秒の巨大なサンクを見ずに評価することができます。

foldl（foldl1）は、中間結果を直ちに評価する方がはるかに効率的であることがわかりません。

厳密左折り目、foldl'とfoldl1'は、それらが（最も外側の値コンストラクタまたはラムダに）弱いヘッド正規形に中間結果を評価し、

last = foldl1' (flip const) 

も非常に効率的であることを行います。

しかし、中間結果がfoldrよりもさらに評価されているので、彼らは少し少なめに効率的である、と、任意のリスト要素が⊥であれば重要なのは、foldl1'バージョンは⊥を返します：

foldl1' f [x1, ⊥, x3, x4] 
    ~> foldl' f x1 [⊥, x3, x4] 
    ~> case f x1 ⊥ of 
      pattern -- that causes ⊥ 
    ~> ⊥ 

foldr1のバージョンでは、リスト要素や中間結果をまったく検査しないため、問題はありません。

---

^（1）fすなわち、2番目の引数に厳密では、単純に2番目の引数を返す

f x ⊥ = ⊥ 

fので、それは明らかにそうであることを意味します。