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
将 和 的序对表示为乘积 对应的整数
(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))
练习 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