理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

もう2章にはいることにする

おひさしぶりのSICP。これを読み終わったとき、きっと違う思考かなにかを手に入れているはずなんだ!と妄想して、久しぶりに再開。1章の内容は読んだんだけど、練習問題が数学寄りだったので、もう2章にすすむことにした。


Schemeにはconsでpair構造を生成し、pairからはcarとcdrで要素を1つ目、2つ目の要素をそれぞれ取り出せる。

重要

一般に、データは選択子と構成子と、これらの手続きを有効な表現とするために満たすべき条件とで定義される。

問題2.1

てわけで正負両方の引数を扱うmake-rat。これで、有理数の表現ができる。あ、でも約分わすれてた。

(define (make-rat n d)
  (if (and (< n 0) (< d 0))
       (cons (* -1 n) (* -1 d))
      (cons n d)))

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

(define (numer x) (car x))
(define (denom x) (cdr x))
問題2.2

同じconsやcarとかで,線分を定義しよう、で線分の中点も計算してやろう。こういうとき、よい子は構成子と選択子をつかわないとダメよっていう練習問題。かんけいないけど、ようやくletを使える機会が!

(define (make-segment p1 p2)
  (cons p1 p2))

(define (start-segment p) (car p))
(define (end-segment   p) (cdr p))

(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))


(define (mid x y) (/ (+ x y) 2.0))

(define (midpoint-segment seg)
  (let ((start-seg (start-segment seg))
        (end-seg   (end-segment   seg)))
    (make-point (mid (x-point start-seg) (x-point end-seg))
                (mid (y-point start-seg) (y-point end-seg)))))
問題2.4

こんなのでも、pair構造は記述できますよ!という関数型言語っぽいトリッキーな例

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))
問題2.5

こんなのでもできる。pairを2^a×3^bで表しておいて、scheme素因数分解というアイデア

(define (cons a b)
  (define (pow n b) 
    (define (sub-pow n b result)
      (if (= b 0) 
          result
          (sub-pow n (- b 1) (* result n))))
    (sub-pow n b 1))
  (* (pow 2 a) (pow 3 b)))

(define (div n divisor)
  (if (= (remainder n divisor) 0)
      (div (/ n divisor) divisor)
      n))

(define (number-of-devide n divisor)
  (define (sub-number-of-devide n divisor cnt)
    (if (= (remainder n divisor) 0)
        (sub-number-of-devide (/ n divisor) divisor (+ cnt 1))
        cnt))
  (sub-number-of-devide n divisor 0))

(define (car z)
  (number-of-devide (div z 3) 2))

(define (cdr z)
  (number-of-devide (div z 2) 3))