Home

SICP - 4 - 用 Selector 和 Pair 进行数据抽象

7/24/2024

实例：有理数的算术运算

(define (gcd x y)
  (if (= y 0)
      x
      (gcd y (remainder x y))))

(define (make-rat n d)
  (let [(divisor (gcd n d))]
    (let [(n* (/ n divisor))
          (d* (/ d divisor))]
      (cond [(> d* 0) (cons n* d*)]
            [(< d* 0) (cons (- n*) (- d*))]))))

(define (numer x) (car x))
(define (denom x) (cdr x))

(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)
  (display (numer x))
  (display "/")
  (display (denom x)))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

(define one-half (make-rat 1 2))
(print-rat one-half) (newline)
(define one-third (make-rat 1 3))
(print-rat one-third) (newline)

(print-rat (add-rat one-half one-third)) (newline)
(print-rat (mul-rat one-half one-third)) (newline)
(print-rat (add-rat one-third one-third)) (newline)

练习 2.1

定义 make-rat 的一个更好的版本

(define (make-rat n d)
  (let [(divisor (gcd n d))]
    (let [(n* (/ n divisor))
          (d* (/ d divisor))]
      (cond [(> d* 0) (cons n* d*)]
            [(< d* 0) (cons (- n*) (- d*))]))))

练习 2.2

线段中点

(define (make-segment start end) (cons start end))
(define (start-segment seg) (car seg))
(define (end-segment seg) (cdr seg))

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

(define (midpoint-segment seg)
  (make-point
   (/ (+ (x-point (start-segment seg))
         (x-point (end-segment seg)))
      2)
   (/ (+ (y-point (start-segment seg))
         (y-point (end-segment seg)))
      2)))

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

(define line (make-segment (make-point 1 2) (make-point 3 4)))
(define mid (midpoint-segment line))
(print-point mid)

练习 2.3

平面矩形的表示

(define (make-segment start end) (cons start end))
(define (start-segment seg) (car seg))
(define (end-segment seg) (cdr seg))

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

(define (make-rect point-lt point-rb) (cons point-lt point-rb))
(define (rect-point-lt rect) (car rect))
(define (rect-point-rb rect) (cdr rect))

(define (rect-width rect) (- (x-point (rect-point-rb rect))
                             (x-point (rect-point-lt rect))))

(define (rect-height rect) (- (y-point (rect-point-lt rect))
                              (y-point (rect-point-rb rect))))

(define (rect-area rect) (* (rect-width rect) (rect-height rect)))
(define (rect-perimeter rect) (* 2 (+ (rect-width rect) (rect-height rect))))

(define rect (make-rect (make-point 1 4) (make-point 3 1)))

(display "Width: ") (display (rect-width rect)) (newline)
(display "Height: ") (display (rect-height rect)) (newline)
(display "Area: ") (display (rect-area rect)) (newline)
(display "Perimeter: ") (display (rect-perimeter rect)) (newline)

序对的其他表示

实例 序对的一种过程性表示

(define (cons x y)
  (define (dispatch m)
    (cond [(= m 0) x]
          [(= m 1) y]
          [else (error "Argument not 0 or 1 -- CONS" m)]))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

(define pair (cons 1 2))

(display (car pair))
(display ", ")
(display (cdr pair))

练习 2.4

序对的另一种过程性表示

(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)))

(define z (cons 1 2))

(display (car z))
(display ", ")
(display (cdr z))

(car z)
(car (lambda (m) (m x y)))
(((lambda (m) (m x y)) (lambda (p q) p)))
((lambda (p q) p) x y)
p

练习 2.5

将 aa 和 bb 的序对表示为乘积 2a⋅3b2^a \cdot 3^b 对应的整数

(define (cons-int a b) (* (expt 2 a) (expt 3 b)))

(define (car-int z)
  (if (= 0 (remainder z 3))
      (car-int (/ z 3))
      (log z 2)))

(define (cdr-int z)
  (log (/ z (expt 2 (car-int z))) 3))

(define pair (cons-int 6 3))

(display (car-int pair))
(display " ")
(display (cdr-int pair))

练习 2.6

丘奇数

(define zero (lambda (f)
               (lambda (x) x)))

(define (add-1 n)
  (lambda (f)
    (lambda (x)
      (f ((n f) x)))))

(define one (lambda (f)
              (lambda (x)
                (f x))))

(define two (lambda (f)
              (lambda (x)
                (f (f x)))))

(define (add m n)
  (lambda (f)
    (lambda (x)
      ((m f) ((n f) x)))))

(define (church->number n)
  ((n (lambda (x) (+ x 1))) 0))

(church->number (add one two))

扩展练习：区间算术

练习 2.7

定义 upper-bound 和 lower-bound

(define (make-interval a b) (cons a b))

(define (upper-bound x) (cdr x))

(define (lower-bound x) (car x))

练习 2.8

定义 sub-interval

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))

练习 2.9

区间的宽度

(define (width x)
  (/ (- (upper-bound x) (lower-bound x)) 2))
(width (add [x1,y1] [x2,y2]))  ⟹  (width [x1+x2,y1+y2])  ⟹  (y1+y2)−(x1+x2)2  ⟹  y1−x12+y2−x22  ⟹  (width [x1,y1])+(width [x2,y2])\begin{aligned} & (\mathrm{width} \ (\mathrm{add}\ [x_1,y_1]\ [x_2,y_2])) \\ \implies & (\mathrm{width}\ [x_1 + x_2, y_1 + y_2]) \\ \implies & \frac{(y_1 + y_2) - (x_1 + x_2)}{2} \\ \implies & \frac{y_1 - x_1}{2} + \frac{y_2 - x_2}{2} \\ \implies & (\mathrm{width}\ [x_1, y_1]) + (\mathrm{width}\ [x_2, y_2]) \end{aligned} (width (sub [x1,y1] [x2,y2]))  ⟹  (width [x1−y2,y1−x2])  ⟹  (y1−x2)−(x1−y2)2  ⟹  y1−x12+y2−x22  ⟹  (width [x1,y1])+(width [x2,y2])\begin{aligned} & (\mathrm{width} \ (\mathrm{sub}\ [x_1,y_1]\ [x_2,y_2])) \\ \implies & (\mathrm{width}\ [x_1 - y_2, y_1 - x_2]) \\ \implies & \frac{(y_1 - x_2) - (x_1 - y_2)}{2} \\ \implies & \frac{y_1 - x_1}{2} + \frac{y_2 - x_2}{2} \\ \implies & (\mathrm{width}\ [x_1, y_1]) + (\mathrm{width}\ [x_2, y_2]) \end{aligned}

练习 2.10

处理被除区间跨过 0 的情况

(define (div-interval x y)
  (if (<= (* (lower-bound y) (upper-bound y)) 0)
      (error "can not divide a span that spans zero.")
      (mul-interval
       x
       (make-interval (/ 1.0 (upper-bound y))
                      (/ 1.0 (lower-bound y))))))

练习 2.11

将 mul-interval 分解为 9 种情况

TODO

练习 2.12

TODO

练习 2.13

TODO

练习 2.14

TODO

练习 2.15

TODO

练习 2.16

TODO