Hatena::Grouphaskell

猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 このページをアンテナに追加 RSSフィード

2015-03-14

遅延評価とfoldr/foldl

| 01:10 | 遅延評価とfoldr/foldl - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

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'を使うという手があるが)。