Haskellメモ:遅延評価と末尾再帰とStack space overflow
dl = [ x/100 | x <- [1..] ]
dlの頭から、指定した値を超えないところまで合計をだす。
sumlist (x:xs) n = if x >= n then 0 else x + sumlist xs n
sumlist dl 10000 とすれば9999.99までの合計がだせるはず。だけど Stack space overflow になってしまう。ここでスタックサイズ増やしちゃったら負け。
末尾再帰になっていないからだ、と考えた場合これで良いはず。
sumlist (x:xs) n acc | x >= n = acc | otherwise = sumlist xs n ( acc + x )
しかし、これもStack space overflow。末尾再帰にしても、遅延評価が積み重なりすぎると、結局オーバーフローしてしまう。
正格評価を使うと解決出来る。acc + xを先に評価してから次の再帰に進む。
sumlist (x:xs) n acc | x >= n = acc | otherwise = acc + x `seq` sumlist xs n ( acc + x )