let t = 関数型プログラミング言語ML 2
■ このスレッドは過去ログ倉庫に格納されています
0647デフォルトの名無しさん
NGNGLazyだと末尾再帰を特別に扱う必要がないことの説明。
あまり巧い説明でないかもしれない…
例:
f 0 s = s
f x s = f (x-1) (s + x)
---
f x sを計算するのに、
Strictな言語は、
f 3 0
-> f 2 3
-> f 1 5
-> f 0 6
-> 6: f 0 6の返り値
-> 6: f 1 5 の返り値
-> 6: f 2 3 の返り値
-> 6
とネストするからナイーブにはスタックがいり、
末尾再帰の最適化が必要になる。
Lazy だと、
f 3 0
-> f (3 - 1) (3 + 0) -- これをまずは返す。
-> f 2 (3 + 0) -- パターンマッチ(0との比較)で (3 - 1)が評価される。
-> f (2 - 1) (2 + (3 + 0))
-> f 1 (3 + 0)
..
-> (1 + (2 + (3 + 0))
-> 6
と評価されるから最適化はいらない。
■ このスレッドは過去ログ倉庫に格納されています