遅延評価とfoldr/foldl

Haskellの遅延評価のイメージは「まず式を立てる（サンクを作る）けど、値の評価はまた別の話」。

foldrは

  foldr f acc [x0, x1, x2, x3, ... , xn]
= x0 `f` (foldr f acc [x1, x2, x3, ... , xn])

= x0 `f` (x1 `f` (x2 `f` (x3 `f` ... `f` (xn `f` acc) ... )))

こんな感じで、カッコの内側である右から計算するように見える式を立てるというイメージ。

が、評価は遅延評価なのでカッコの外側つまり左から評価するので、そのたびごとにリスト [x0, x1, ... , xn] を1つづつバラしていくことが可能。よって途中で打ち切る場合なら無限リストでも問題にならない。

foldlは

  foldl f acc [x0, x1, x2, x3, ... , xn]
= foldl f (acc `f` x0) [x1, x2, x3, ... , xn]

= ... ((((acc `f` x0) `f` x1) `f` x2) `f` x3) `f` ...  `f` xn

こんな感じで、カッコの内側である左から計算するように見える式を立てるいうイメージ。

が、評価は遅延評価なのでカッコの外側つまり右から評価するので、リスト [x0, x1, ... , xn] は全部バラさないといけないから、無限リストだと計算が終わらなくなるし、有限リストでもメモリをたくさん必要とする（メモリについてはfoldl'を使うという手があるが）。