构造数据抽象

抽象是克服复杂性的一种技术。

1. 练习 2.1

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

2. 练习 2.2

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

(define (x-point i) (car i))
(define (y-point i) (cdr i))

(define (make-segment i j)
  (cons i j))

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

(define (midpoint-segment s)
  (define (average x y) (/ (+ x y) 2))
  (let ((midpoint-x (average (x-point (start-segment s))
                             (x-point (end-segment s))))
        (midpoint-y (average (y-point (start-segment s))
                             (y-point (end-segment s)))))
    (make-point midpoint-x midpoint-y)))

3. 练习2.5

(define (cons x y)
    (* (expt 2 x)
       (expt 3 y)))

(define (car z)
    (if (= 0 (remainder z 2))
        (+ 1 (car (/ z 2)))
        0))

(define (cdr z)
    (if (= 0 (remainder z 3))
        (+ 1 (cdr (/ z 3)))
        0))

4. 练习2.17

(define (last-pair items)
  (define (get-last it pair)
    (if (null? it)
        pair
        (get-last (cdr it) (car it))))
  (get-last (cdr items) (car items)))

(define (last-pair lst)
    (cond ((null? lst)
            (error "list empty -- LAST-PAIR"))
          ((null? (cdr lst))
            lst)
          (else
            (last-pair (cdr lst)))))

5. 练习2.18

(define (reverse items)
  (define (reverse-iter it1 it2)
    (if (null? it1)
        it2
        (reverse-iter (cdr it1)
                      (cons (car it1)
                            it2))))
  (reverse-iter items (list)))

6. 递归求树的叶子数

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

7. 练习2.27

人的代码：

(define (deep-reverse-recu tree)
   (cond ((null? tree)
          tree)
         ((not (pair? tree)) tree)
         (else
          (append (deep-reverse-recu (cdr tree))
                  (list (deep-reverse-recu (car tree)))))))

神的代码：

(define (deep-reverse L)
  (if (pair? L)
      (reverse (map deep-reverse L))
      L))

8. 练习2.28

递归
(define (fringe tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (append (if (null? (car tree))
                          (list (car tree))
                          (fringe (car tree)))
                      (fringe (cdr tree))))))

迭代
(define (fringe tree)
  (define (iter tree result)
    (cond ((null? tree) result)
          ((not (pair? tree)) (append result
                                      (list tree)))
          (else (append (if (null? (car tree))
                            (list (car tree))
                            (fringe (car tree)))
                        (fringe (cdr tree))))))
  (iter tree '()))

9. 练习2.30

(define (square-list tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-list sub-tree)
             (square sub-tree)))
       tree))

10.练习2.31

(define (tree-map fun tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (tree-map fun sub-tree)
             (fun sub-tree)))
       tree))

11.练习2.32

(define (subsets s)
    (if (null? s)
        (list '())
        (let ((rest (subsets (cdr s))))
            (append rest (map (lambda (x)
                                (cons (car s) x))
                              rest)))))

解释：集合S的子集是(cdr S)的子集+对(cdr S)里每个元素append上(car S)。

12. 练习2.35

(define (count-leaves tree)
    (accumulate +
                0
                (map (lambda (sub-tree)
                         (if (pair? sub-tree)           ; 如果这个节点有分支
                             (count-leaves sub-tree)    ; 那么这个节点调用 count-leaves 的结果就是这个节点的树叶数量
                             1))                        ; 遇上一个叶子节点就返回 1
                     tree)))

13. 练习2.41

(define (enumerate-int-reverse low high)
  (if (> low high)
      '()
      (cons high (enumerate-int-reverse low (- high 1)))))

(define (three-pairs n)
  (accumulate append
              '()
              (map (lambda (i)
                     (map (lambda (j) (cons i j))
                          (unique-pairs (- i 1))))
                   (enumerate-int-reverse 1 n))))


(define (choose-pair n s)
  (define (three-sum? item)
    (define (three-sum item)
      (if (null? item)
          0
          (+ (car item)
             (three-sum (cdr item)))))
    (if (= s (three-sum item))
        #t
        #f))
  (filter three-sum?
          (three-pairs n)))

14. 练习2.42（八皇后问题）

搜索+剪枝

(define empty-board '())

(define (safe? k positions)
  (define k-position (car positions))
  (define (safe-pos pos)
    (if (null? pos)
        #t
        (cond ((= (cdr (car pos)) (cdr k-position)) #f)
              ((= (abs (- (cdr (car pos)) (cdr k-position)))
                  (abs (- (car (car pos)) (car k-position))))
               #f)
              (else (safe-pos (cdr pos))))))
  (safe-pos (cdr positions)))

(define (adjoin-position new-row k rest-of-queens)
  (define k-position (list (cons k new-row)))
  (append k-position rest-of-queens))


(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

15. 练习2.54

(define (equal? a b)
 (if (and (pair? a) (pair? b))
     (and (equal? (car a) (car b))
          (equal? (cdr a) (cdr b)))
     (eq? a b)))