Exercise 2.29 · 习题

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

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.

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

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.

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?

Mapping over trees

Just as map is a powerful abstraction for dealing with sequences,
map together with recursion is a powerful abstraction for dealing with
trees. For instance, the scale-tree procedure, analogous to
scale-list of 2.2.1, takes as arguments a numeric factor
and a tree whose leaves are numbers. It returns a tree of the same shape,
where each number is multiplied by the factor. The recursive plan for
scale-tree is similar to the one for count-leaves:

(define (scale-tree tree factor)
(cond ((null? tree) nil)
((not (pair? tree))
(* tree factor))
(else
(cons (scale-tree (car tree)
factor)
(scale-tree (cdr tree)
factor)))))

(scale-tree (list 1
(list 2 (list 3 4) 5)
(list 6 7))
10)

(10 (20 (30 40) 50) (60 70))

Another way to implement scale-tree is to regard the tree as a sequence
of sub-trees and use map. We map over the sequence, scaling each
sub-tree in turn, and return the list of results. In the base case, where the
tree is a leaf, we simply multiply by the factor:

(define (scale-tree tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree sub-tree factor)
(* sub-tree factor)))
tree))

Many tree operations can be implemented by similar combinations of sequence

operations and recursion.

练习 2.29：一个二叉活动体 (binary mobile) 由两条分支组成：左分支和右分支。每条分支是一根有一定长度的杆，杆上悬挂着一个重物或另一个二叉活动体。我们可以用复合数据来表示二叉活动体，将其由两条分支构成（例如，使用 list）：

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

一条分支由一个长度（必须是数）和一个结构构成，结构可以是一个数（表示简单的重物）或另一个活动体：

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

写出相应的选择函数 left-branch 和 right-branch（返回活动体的两条分支），以及 branch-length 和 branch-structure（返回分支的各组成部分）。

利用你的选择函数，定义一个过程 total-weight，返回一个活动体的总重量。

若一个活动体顶部左分支施加的力矩等于顶部右分支施加的力矩（即左杆长度乘以悬挂重量等于右侧对应乘积），且其各分支上悬挂的每个子活动体也都是平衡的，则称该活动体是平衡的 (balanced)。设计一个谓词，检验一个二叉活动体是否平衡。

假设我们改变活动体的表示方式，使构造函数变为

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

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

为了将程序转换为新的表示，你需要做多少改动？

对树进行映射

正如 map 是处理序列的有力抽象手段，map 与递归相结合同样是处理树的有力抽象手段。例如，过程 scale-tree 类似于第 2.2.1 节的 scale-list，它以一个数值因子和一棵叶子均为数的树为参数，返回形状相同的树，其中每个数都乘以该因子。scale-tree 的递归方案与 count-leaves 类似：

(define (scale-tree tree factor)
(cond ((null? tree) nil)
((not (pair? tree))
(* tree factor))
(else
(cons (scale-tree (car tree)
factor)
(scale-tree (cdr tree)
factor)))))

(scale-tree (list 1
(list 2 (list 3 4) 5)
(list 6 7))
10)

(10 (20 (30 40) 50) (60 70))

实现 scale-tree 的另一种方式是把树视为子树的序列，并使用 map。我们对该序列进行映射，依次对每棵子树进行缩放，并返回结果的表。在基本情况下，当树是一片叶子时，直接乘以因子即可：

(define (scale-tree tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree sub-tree factor)
(* sub-tree factor)))
tree))

许多树的操作都可以通过序列操作与递归的类似组合来实现。