作业 2

CS61AS 第 2 课作业：lambda、高阶函数与 SICP 练习。

模板

在终端输入下面的命令，把模板文件复制到当前目录（注意末尾有一个点）：

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

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

自动评分器

如果你在实验室的计算机上工作，grader 命令会运行自动评分器（autograder）。如果你在自己的个人电脑上工作，你应该下载 grader.rkt 和 作业 2 测试。

练习 1

编写一个过程 substitute，它接受三个实参：一个句子（sentence）、一个旧词和一个新词。它应该返回句子的一个副本，但其中旧词的每一次出现都要替换为新词。

-> (substitute '(she loves you yeah yeah yeah) 'yeah 'maybe)
(she loves you maybe maybe maybe)

练习 2

把下面每一条输入 Racket，记下结果。尽量在让 Racket 计算之前先自己预测结果。

(lambda (x) (+ x 3))
((lambda (x) (+ x 3)) 7)

make-adder 是一个返回另一个函数的函数。

(define (make-adder num)
  (lambda (x) (+ x num)))
((make-adder 3) 7)
(define plus3 (make-adder 3))
(plus3 7)
(define (square x) (* x x))
(square 5)
(define sq (lambda (x) (* x x)))
(sq 5)
(define (try f) (f 3 5))
(try +)
(try word)

练习 3

考虑一个函数 g，表达式

((g) 1)

求值后返回 3。

判断 g 有几个实参。并用一个词尽可能描述 g 返回的值的类型。

练习 4

对于下面每个表达式，f 必须是什么，才能让表达式的求值成功、不引发错误？对于每个表达式，给出一个 f 的定义，使得求值该表达式不会引发错误，并说出在你的定义下该表达式的值是多少。明确一下：对于第 1 条，定义 f1；第 2 条，定义 f2，依此类推。

  1. f1
  2. (f2)
  3. (f3 3)
  4. ((f4))
  5. (((f5)) 3)

练习 5

求下列表达式的值，其中 add1 是给实参加 1 的内置过程，t 定义如下：

(define (t f)
  (lambda (x) (f (f (f x)))) )

先在纸上算出来，再上机验证。

  1. ((t add1) 0)
  2. ((t (t add1)) 0)
  3. (((t t) add1) 0)

练习 6

求下列表达式的值，其中 t 的定义与练习 5 相同，s 定义如下：

(define (s x)
  (+ 1 x))

先在纸上算出来，再上机验证。

  1. ((t s) 0)
  2. ((t (t s)) 0)
  3. (((t t) s) 0)

练习 7

编写并测试 make-tester 过程。给定一个词 w 作为实参，make-tester 返回一个单实参过程 x：如果 x 等于 w，返回 true，否则返回 false。

-> ((make-tester 'hal) 'hal)
#t
-> ((make-tester 'hal) 'cs61a)
#f
-> (define sicp-author-and-astronomer? (make-tester 'gerry))
-> (sicp-author-and-astronomer? 'hal)
#f
-> (sicp-author-and-astronomer? 'gerry)
#t

练习 8

完成 SICP 练习 1.31a、1.32a、1.33、1.40、1.41 和 1.43。其中部分题目需要阅读 SICP 正文的相关内容。

一些补充指引：

  • 对于 1.31a，你应该基于课文前面的 sum 函数来编写你的 product 函数。它应该接受四个实参（term、a、next 和 b）。找到 sum 函数，弄清每个实参的作用。
  • 对于 1.31a，用于估计 π 的函数应命名为 estimate-pi（见模板）。它不接受实参，应使用题目所给公式的前至少 100 项来估计 π。
  • 对于 1.33，谓词（predicate）应该是 filtered-accumulate 的最后一个实参（见模板）。
  • 对于 1.33，你应该定义函数 sum-sq-prime 和 prod-of-some-numbers（见模板）。
  • 对于 1.40，不必费心学习牛顿法。只需完成 cubic，它接受三个实参（a、b 和 c）并返回另一个过程。这个过程接受输入 x，并在 x 处求题目中三次多项式的值。
  • 对于 1.43，把你的过程命名为 my-repeated 而不是 repeated（见模板）。

练习 9

上周你编写了过程 squares，它对实参句子中的每个数求平方；你还见过 pigl-sent，它对实参句子中的每个词做 pigl 处理。把这一模式推广，创建一个名为 my-every 的高阶过程，把作为实参传入的任意过程应用到实参句子的每个词上。

-> (my-every square '(1 2 3 4))
(1 4 9 16)
-> (my-every first '(nowhere man))
(n m)

练习 10

利用高阶函数：我们的 simply-scheme 库提供了上一个练习中 every 函数以及课上讲过的 keep 函数自己的版本。先在纸上完成下面这些例子，再上机验证，熟悉这两个函数：

  1. (every (lambda (letter) (word letter letter)) 'purple)
  2. (every (lambda (n) (if (even? n) (word n n) n)) '(781 5 76 909 24))
  3. (keep even? '(781 5 76 909 24))
  4. (keep (lambda (letter) (member? letter 'aeiou)) 'bookkeeper)
  5. (keep (lambda (letter) (member? letter 'aeiou)) 'syzygy)
  6. (keep (lambda (letter) (member? letter 'aeiou)) '(purple syzygy))
  7. (keep (lambda (wd) (member? 'e wd)) '(purple syzygy))

提交作业！

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

如果在提交过程中遇到任何麻烦，请随时向助教（TA）求助！