let t = 関数型プログラミング言語ML 2
■ このスレッドは過去ログ倉庫に格納されています
0571デフォルトの名無しさん
NGNGLazyの欠点は、次にしないといけないことをずっと覚えておく必要があり、
それがメモリを圧迫する可能性があること。
もう一つは、tail recursion でよく表れるような罠かな。
> sum [] s = s
> sum (x:xs) s = sum xs (x + s)
> -- 例: sum [1,2,3] 0 == 6
> -- [1,2,3] == (1:2:3:[])
このsumはtail recursiveだが、sum [1..n] 0 はnが大きいときにstack overflowする。
なぜか?
sは最後まで必要でないので+が計算されず、
sum [] s = s にいたって初めて、 n + x_{n-1} を計算しようとし、
(ここで、x_{n - 1} = (n - 1) + x_{n-2}, ...)
結局、sum (x:xs) = x + sum xs と順序が逆なだけで、
同じ様にスタックを必要としてしまうからだ。
解決法の一つは、accumulatorについてstrictにすること。
> sum (x:xs) s = sum xs $! (x + s)
GHCコンパイラはこの程度のことは最適化で自動でやってくれる。
利点は、>>570が述べたとおり。記述力が違う。慣れるとやめられん。
■ このスレッドは過去ログ倉庫に格納されています