SICP 練習問題 1.6〜1.10

つづいて、さっきまで取り組んでいた練習問題1.6〜1.10の解答を掲載。

;------------------------------
; 1.6
; 特殊形式 if について。（要するに、オペレータではなくて構文だよって言いたいってこと？）
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (new-sqrt x)
  (let loop ((count 5)
             (src x))
    (new-if (= count 0)
            (exact->inexact src)
            (loop #?=(- count 1) #?=(/ (+ src (/ x src)) 2)))))

;;-> 構文のifならば、第１引数が評価された後に、第２引数、
;;   または第３引数の「どちらか一方が」評価される。
;;   したがって、終了条件が明確になるためちゃんと終了することができる。
;;   翻って、new-ifは単なるオペレータであるため、new-ifで定義している処理を評価する前に、
;;   第１引数から第３引数までが先に評価されてしまう。
;;   つまり、無条件に第３引数の「(loop (- count 1) (/ (+ src (/ x src)) 2))」が評価されてしまい、
;;   無限再帰することになってしまう。
;;   coutはマイナス無限大になっていき、srcは限りなく正しい値に漸近していく感じ？
;;   「#?=」つけてみたら、なんとなくそんな感じにはなってたぞ。


;------------------------------
; 1.7
;;-> すんません、ちょっとすっ飛ばしたい感じなのでそうします。。
;;   （これでもかつては物理専攻でした。。）


;------------------------------
; 1.8
(define (root x proc)
  (let loop ((count 6)
             (src x))
    (if (= count 0)
        (exact->inexact src)
        (loop (- count 1) (proc x src)))))

(define (sqrt x)
  (root x (lambda (x src) (/ (+ src (/ x src)) 2))))

(define (3root x)
  (root x (lambda (x src) (/ (+ (/ x (* src src)) (* 2 src)) 3))))


;;========================================
;;1.9の前に、再帰的 or 反復的 のお勉強を。
;;========================================
; 1.2.1 線形再帰と反復
; n! = n・(n-1)・(n-2)... 3・2・1
(define (factorial1 n)
  (if (= n 1)
      1
      (* n (factorial1 (- n 1)))))

(define (factorial2 n)
  (let loop ((seed n)
             (ans 1))
    (if (= seed 1)
        ans
        (loop (- seed 1) (* ans seed)))))
;; factorial2だとtraceが使えないのでちょこっと変更。
;; ちなみにtraceを利用するには、
;; ------------------------------
;; gosh> (use slib)
;; gosh> (require 'trace)
;; ------------------------------
;; とやって、
;; ------------------------------
;; gosh> (trace factorial1)
;; #
;; ------------------------------
;; とやった上で、関数を評価してやると、こんな風にでる。
;; ------------------------------
;; gosh> (factorial1 5)
;; CALL factorial1 5
;;  CALL factorial1 4
;;   CALL factorial1 3
;;    CALL factorial1 2
;;    RETN factorial1 2
;;   RETN factorial1 6
;;  RETN factorial1 24
;; RETN factorial1 120
;; 120
;; ------------------------------
(define (f-iter seed ans)
  (if (= seed 1)
      ans
      (f-iter (- seed 1) (* ans seed))))

(define (factorial3 n)
  (f-iter n 1))

;; すんごい適当な理解だけど、SICPで言及されてる「反復的」「再帰的」ってのは、
;; ・反復的 → 末尾再帰
;; ・再帰的 → 非末尾再帰
;; って解釈でいいんかな？

;------------------------------
; 1.9
(define (dec x) (- x 1))
(define (inc x) (+ x 1))

(define (plus a b)
  (if (= a 0)
      b
      (inc (plus (dec a) b))))

(define (plus2 a b)
  (if (= a 0)
      b
      (plus2 (dec a) (inc b))))
;;-> plusはincで入れ子になってく。plus2は末尾再帰してると思う。


;------------------------------
; 1.10
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

;;-> (A 1 10) -> 1024
;;-> (A 2 4)  -> 65536
;;-> (A 3 3)  -> 65536

(define (f n) (A 0 n))   ;-> ２n？
(define (g n) (A 1 n))   ;-> ２^n？
(define (h n) (A 2 n))   ;-> すんません、マジわかりません。。
(define (k n) (* 5 n n)) ;-> 5n^2

1.7が面倒くさそうでやめちまったい。後で後悔するかなぁ。。
あと、1.10はマジわかんね。何コレ？
誰か知ってる人教えてください。

俺数学じゃなくてSchemeをやりたいんだけどなぁ〜。

−