作业 5

模板

在终端中输入下面内容，把模板文件复制到当前目录（注意末尾的句点）：

cp ~cs61as/autograder/templates/hw5.rkt .

或者，你可以从这里下载模板。

自动评分器

如果你在实验室的电脑上做作业，grader 命令会运行自动评分器。如果你在自己的个人电脑上做作业，你应该下载 grader.rkt 和作业 5 测试。

练习 1：SICP 2.26

假设我们把 x 和 y 定义为两个列表：

(define x (list 1 2 3))
(define y (list 4 5 6))

解释器对以下每个表达式求值后会打印什么结果？

(append x y)
(cons x y)
(list x y)

练习 2：SICP 2.29

一个二叉移动（binary mobile）由两条分支组成——左分支和右分支。每条分支是一根定长的杆，杆上挂着要么是一个重物，要么是另一个二叉移动。我们可以用复合数据来表示二叉移动，比如用两个分支构造它（例如用 list）：

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

一条分支由长度（必须是数字）和挂在它上面的结构组成，这个结构可以是数字（表示一个简单的重物），也可以是另一个移动：

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

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

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

c. 如果一个移动的左分支产生的力矩等于右分支产生的力矩（即左杆长度乘以杆上所挂重物的重量，等于右侧相应的乘积），并且挂在两条分支上的每个子移动都是平衡的，我们就说这个移动是平衡的（balanced）。设计一个谓词，检验一个二叉移动是否平衡。

d. 假设我们改变移动的表示方式，使构造函数变成

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

要把程序转换到新的表示方式，你需要做多少改动？

练习 3：SICP 2.30、2.31

a. 定义一个与 square-list 过程类似的过程 square-tree。也就是说，square-tree 的行为应如下所示：

> (square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
(1 (4 (9 16) 25) (36 49))

b. 对你的答案进行抽象，产出一个过程 tree-map，使得 square-tree 可以这样定义：

(define (square-tree tree) (tree-map square tree))

练习 4：SICP 2.36

过程 accumulate-n 与 accumulate 类似，区别在于它的第三个参数是一个序列的序列，并假定它们都含有相同数量的元素。它把指定的累加过程分别作用于各个序列的第一个元素、各个序列的第二个元素，以此类推，并返回一个由结果组成的序列。例如，如果 s 是包含四个序列的序列 ((1 2 3) (4 5 6) (7 8 9) (10 11 12))，那么 (accumulate-n + 0 s) 的值应该是序列 (22 26 30)。补全下面 accumulate-n 定义中缺失的表达式：

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init <??>)
            (accumulate-n op init <??>))))

练习 5

假设我们用数的序列表示向量 $v = (v_i)$，用向量（矩阵的行）的序列表示矩阵 $m = (m_{i,j})$。例如，矩阵

表示为序列 ((1 2 3 4) (4 5 6 6) (6 7 8 9))。有了这种表示，我们可以用序列操作来简洁地表达基本的矩阵和向量运算。这些运算（任何矩阵代数教材中都有描述）如下：

我们可以这样定义点积：

(define (dot-product v w)
    (accumulate + 0 (map * v w)))

补全下面计算其他矩阵运算的过程中缺失的表达式。（过程 accumulate-n 在上一练习中定义）

(define (matrix-*-vector m v)
  (map <??> m))

(define (transpose mat)
  (accumulate-n <??> <??> mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map <??> m)))

练习 6：SICP 2.38

accumulate 过程也称为 fold-right，因为它把序列的第一个元素与组合其余所有元素的结果组合起来。还有一个 fold-left，它与 fold-right 类似，只不过按相反的方向组合元素：

(define (fold-left op initial sequence)
    (define (iter result rest)
        (if (null? rest)
            result
            (iter (op result (car rest))
                  (cdr rest))))
    (iter initial sequence))

下面这些值分别是多少？

(fold-right / 1 (list 1 2 3))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 1 2 3))

描述 op 应满足的一个性质，以保证 fold-right 和 fold-left 对任何序列都产生相同的值。

练习 7：SICP 2.54

如果两个列表含有按相同顺序排列的相等元素，我们就说这两个列表相等。例如，

(equal? '(this is a list) '(this is a list))

为真，但

(equal? '(this is a list) '(this (is a) list))

为假。更准确地说，我们可以在符号的 eq? 相等性基础上递归地定义 equal?：如果 a 和 b 都是符号且它们 eq?，或者它们都是列表且 (car a) 与 (car b) equal?、(cdr a) 与 (cdr b) equal?，那么 a 和 b 就 equal?。用这个思路把 equal? 实现为一个过程。

注意：你现在应该已经知道 equal? 也是一个内置过程。这意味着你的定义会覆盖内置定义。

练习 8

我们可以用互异元素的列表表示一个集合，用列表的列表表示一个集合的所有子集组成的集合。例如，如果集合是 (1 2 3)，那么所有子集组成的集合是 (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))。补全下面这个生成集合的所有子集的过程定义，并清楚解释它为什么能工作：

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))

练习 9

扩展 calc.rkt，把单词也作为数据纳入，提供 first、butfirst、last、butlast 和 word 这些操作。与 Racket 不同，你的计算器应该把单词当作自求值表达式，除非它出现在复合表达式的运算符位置。也就是说，它应该像下面这些例子这样工作：

calc: foo
foo
calc: (first foo)
f
calc: (first (butfirst hello))
e

记住，你可以输入下面这行获取程序

cp ~cs61as/lib/calc.rkt .

或者从这里下载。

练习 10：学有余力者进阶

阅读第 2.3.4 节，并完成练习 2.67 - 2.72。

练习 11：学有余力者进阶

示例编程：在某些编程系统中，你不必编写算法，而是给出你希望程序如何表现的例子，由语言自己推导出算法：

> (define pairup (regroup '((1 2) (3 4) ...)))
> (pairup '(the rain in spain stays mainly on the plain))
((the rain) (in spain) (stays mainly) (on the))

编写 regroup。阅读 ~cs61as/lib/regroup.problem 了解详情。

提交作业！

相关说明请参见这份指南。它涵盖基本终端命令和作业提交。

提交时如有任何困难，尽管找 TA！