問題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の場合、同じような計算式が木構造のような感じで伸びていくので、メモリを消費しやすい、ってことも言えるかな。