すごいH本 part30

モジュールを使う。の続き

foldlがスタックオーバーフローを起こすことがあるのでそれを見てゆく。

*Main> foldl (+) 0 (replicate 100000000 1)
*** Exception: stack overflow

Haskell は遅延評価なので実際の値の計算は可能な限り後まで引き伸ばされる。 評価するための計算をメモリ上に保持していくので計算量が多くなりすぎるとメモリ上限に達する。

foldl の計算の様子

foldl (+) 0 [1,2,3] =
foldl (+) (0 + 1) [2,3] =
foldl (+) (0 + 1 + 2) [3] =
foldl (+) (0 + 1 + 2 + 3) [] =
((0 + 1) + 2) + 3 =
(1 + 2) + 3 =
3 + 3 =
6 

スタックオーバーフローさせないようにするために、Data.List.foldl'という正格バージョンの関数が用意されている。

*Main> foldl' (+) 0 (replicate 100000000 1)
100000000

foldl1に対するfoldl1'なども用意されている。

所感

畳み込みの計算の様子がわかりやすいし、遅延評価の仕組みが知れた。

すごいHaskellたのしく学ぼう！