SICP 全笔记

Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

(define (make-mobile left right)
  (list left right))

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

(define (make-branch length structure)
  (list length structure))

a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

d. Suppose we change the representation of mobiles so that the constructors are

(define (make-mobile left right)
  (cons left right))
(define (make-branch length structure)
  (cons length structure))

How much do you need to change your programs to convert to the new representation?

选择函数

(define (make-mobile left right)
  (list left right))

;;; a)
;; selectors
(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (cadr mobile))

(define (make-branch length structure)
  (list length structure))

(define (branch-length branch)
  (car branch))

(define (branch-strucuture branch)
  (cadr branch))

;; a) tests begin
(load "../testframe.scm")

(let ((mobile (make-mobile (make-branch 2 34)
                           (make-branch 3 45))))
  (assert= (branch-length (left-branch mobile)) 2)
  (assert= (branch-strucuture (right-branch mobile)) 45))

total-weight

一个不恰当的 total-weight 可能如下：


;;; b)
;; total-weight: return the total weight of a mobile
(define (total-weight mobile)
  (define (branch-weight branch)
    (cond ((pair? (branch-strucuture branch)) ; it is a mobile
           (total-weight (branch-strucuture branch)))
          (else
           (branch-strucuture branch))))
  (+ (branch-weight (left-branch mobile))
     (branch-weight (right-branch mobile))))

这个 total-weight 的不恰当之处是在于去直接判断一个结构是不是 mobile，但我们的构造中并没有办法去得知一个结构是不是 mobile。思考问题时候的思路应该是如何判断它是不是一个 branch，而不是去判读是否是 mobile。

(define (total-weight mobile)
  (define (branch-weight branch)
    (cond ((number? (branch-strucuture branch))
           (branch-strucuture branch))
          (else
           (total-weight (branch-strucuture branch)))))
  (+ (branch-weight (left-branch mobile))
     (branch-weight (right-branch mobile))))

;; b) tests begin
(let ((test-mobile
       (make-mobile
        (make-branch 2 (make-mobile (make-branch 4 3)
                                    (make-branch 6 12)))
        (make-branch 3 (make-mobile (make-branch 19 20)
                                    (make-branch 22 31))))))
  (assert= (total-weight test-mobile) 66))

balanced?

balanced? 将接受一个 mobile 作为参数，递归去 left 和 right 查看是否平衡，以及当前 mobile 是否平衡。因为作为参数的 mobile 可能为上一个分支的 structure，可能为数字，所以下面的 balanced? 需要判读这个 structure 是一个数字还是另外一个活动体：

;; balanced? test case:

; submobile is not balanced!
(define unbalanced-mobile
  (make-mobile (make-branch 100 (make-mobile (make-branch 4 10)
                                             (make-branch 5 10)))
               (make-branch 20 (make-mobile (make-branch 6 50)
                                            (make-branch 7 50)))))
(define balanced-mobile-1
  (make-mobile (make-branch 100 (make-mobile (make-branch 100 20)
                                             (make-branch 20 100)))
               (make-branch 20 (make-mobile (make-branch 10 300)
                                            (make-branch 10 300)))))

(define balanced-mobile-2
  (make-mobile (make-branch 100 22)
               (make-branch 20 (make-mobile (make-branch 10 100)
                                            (make-branch 100 10)))))

(define balanced-mobile-3
  (make-mobile (make-branch 100 22)
               (make-branch 22 100)))

(define (balanced? mobile)
  (define (branch-weight branch)
    (if (number? (branch-strucuture branch))
        (branch-strucuture branch)
        (total-weight (branch-strucuture branch))))
  (cond ((number? mobile) #t)
        (else
         (let ((left (left-branch mobile))
               (right (right-branch mobile)))
           (cond ((not (= (* (branch-length left)
                             (branch-weight left))
                          (* (branch-length right)
                             (branch-weight right))))
                  #f)
                 ((not (and (balanced? (branch-strucuture left))
                            (balanced? (branch-strucuture right))))
                  #f)
                 (else #t))))))


;; c) tests begin
(asserteq? (balanced? unbalanced-mobile) #f)
(asserteq? (balanced? balanced-mobile-1) #t)
(asserteq? (balanced? balanced-mobile-2) #t)
(asserteq? (balanced? balanced-mobile-3) #t)

在 《Ansi Common Lisp》 中， Paul 总结了写递归函数的诀窍。

这里的 balanced? 不是复杂的过程，但一旦混淆了 branch 和 mobile 两个结构，或者没有看出传递到 balanced? 中的可能是数字，那么 balanced? 是很难又快又准地写出来的。

更改底层结构

即使我们更改了 make-branch 和 make-mobile，我们也只需要修改选择函数就可以。这个练习再次体现了“数据抽象”的好处。