問題1.20
最大公約数の問題をNormal-Orderで展開したときと、Applicative-Orderで展開したときでトレースしろってことかな?
てことで、真面目にやってみた(かなりはしょったけど)。
まず、Normal-Order
(gcd 206 40) ;=> (gcd 40 (rem 206 40))) ;=> (gcd (rem 206 40) (rem 40 (rem 206 40)))) ;=> (gcd (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))) ;=> (gcd (rem (rem 206 40) (rem 40 (rem 206 40))) (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))))) ;=> (ここで述語がtrueに) (rem (rem 206 40) (rem 40 (rem 206 40))) ;=> (rem 6 4) ;=> 2
何か気が狂いそう。
ちなみに、Applicative-Orderの場合
(gcd 206 40) ;=> (gcd 40 (rem 206 40)) ;=> (gcd 40 6) ;=> (gcd 6 (rem 40 6)) ;=> (gcd 6 4) ;=> (gcd 6 (rem 6 4)) ;=> (gcd 6 2) ;=> (gcd 2 (rem 6 2)) ;=> (gcd 2 0) ;=> ここで述語が成立 2
超シンプル。結局結論がわからないのだが、この計算で行くと、Applicative-Orderの方が効率がいいよ、ってことか。Normal-Orderの場合、同じような計算式が木構造のような感じで伸びていくので、メモリを消費しやすい、ってことも言えるかな。