再次填坑。

笔记

本章主要讲了过程作为第一公民的用法与作用。

主要有四点

  • 过程可以通过变量命名
  • 过程可以通过参数传递
  • 过程可以通过过程返回
  • 过程可以包含在结构中

Scheme 语言在这方面比较灵活。不像有的语言想要传递一个过程还得要先封装一个类通过实例才能传递。更不像有的语言一个 lambda 语法设计得那么复杂又没有品味。

习题

习题 1.29

Exercise 1.29. Simpson’s Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson’s Rule, the integral of a function $f$ between $a$ and $b$ is approximated as
$$
\frac{h}{3}[y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + …+ 2y_{n-2} + 4y_{n-1} + y_n]
$$
where $h = (b - a)/n$ , for some even integer $n$, and $y_k = f(a + kh)$. (Increasing $n$ increases the accuracy of the approximation.) Define a procedure that takes as arguments $f$, $a$, $b$, and $n$ and returns the value of the integral, computed using Simpson’s Rule. Use your procedure to integrate cube between 0 and 1 (with $n = 100$ and $n = 1000$), and compare the results to those of theintegral procedure shown above.

这道题要用到之前的求和函数。

显然需要的求和的部分就是一系列的 $y$ 。

范围为 $[0,n]$ 。

通过观察可以发现 $y_m$ 前面的系数 $times$ 的规律为
$$
times =
\begin{cases}
1, & m = 0,n
\2, & m \bmod 2 = 0
\4, & m \bmod 2 = 1
\end{cases}
$$
然后按照公式翻译成代码就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
         
(define (integral f a b n)
    (define h (/ (- b a) n))
    (define (y k) (f (+ a (* k h))))
    (define (times m)
            (if (even? m) 2 4))
    (define (item m)
        (cond ((= m 0) (y m))
              ((= m n) (y n))
              (else (* (times m) (y m)))))
    (define (inc x) (+ x 1))
    (* (/ h 3) (sum item 0 inc n)))
    
(define (cube x) (* x x x))

测试

1
2
(integral cube 0 1 100)
; 1/4

习题 1.30

Exercise 1.30. The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

1
2
3
4
5
6
(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

这道题只需要找出迭代的退出边界和迭代的等式就可以了。

显然退出的条件与递归一致，当下边界 $a$ 大于上边界 $b$ 时退出。

递推式为
$$
result = result + term(a)
$$
所以答案是

1
2
3
4
5
6
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
  (iter a 0))

测试

1
2
3
4
(define (identity x) x)
(define (inc x) (+ x 1))
(sum identity 1 inc 100)
; 5050

习题 1.31

Exercise 1.31.
a. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.51 Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to $\pi$ using the formula 52

$$
\frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdot …}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdot …}
$$
b. If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

仿照 sum 编写，把其中的 + 替换成 * 即可。

1
2
3
4
5
(define (product term a next b)
    (if (> a b)
        1
        (* (term a)
            (product term (next a) next b))))

接着求 $\pi$ 的近似值。

$\frac{\pi}{4}$ 的展开式可以拆成一个个分数连乘，也可以看作两个连乘做除法。

这里选择当作两个连乘序列来处理。

分子序列 $n_k$ 通过观察可得
$$
n_k = \lfloor k / 2\rfloor \times 2 + 2
$$
分母序列 $m_k$ 通过观察可得
$$
m_k = \lfloor (k+1)/2 \rfloor \times 2 + 1
$$
做除法即可

1
2
3
4
5
6
7
8
9
10
11
(define (n k) (+ (* (quotient k 2) 2) 2.0))

(define (m k) (+ (* (quotient (+ k 1) 2) 2) 1.0))

(define (identity x) x)

(define (inc x) (+ x 1))

(define (pi k)
    (* 4 (/ (product n 1 inc k)
            (product m 1 inc k))))

测试

1
2
3
(pi 100)
; 3.1570301764551667
; 收敛得很慢

接着实现阶乘。

阶乘的定义为
$$
n! = n \times (n-1) \times (n-2) \times … \times 2 \times 1
$$
所以从 $1$ 乘到 $n$ 即可。

1
2
3
4
(define (factorial n)
    (define (identity x) x)
    (define (inc x) (+ x 1))
    (product identity 1 inc n))

测试

1
2
(factorial 5)
; 120

然后把递归形式改成迭代形式。参照 sum 可得

1
2
3
4
5
6
(define (product term a next b)
    (define (iter a result)
        (if (> a b)
            result
            (iter (next a) (* result (term a)))))
    (iter a 1))

习题 1.32

Exercise 1.32. a. Show that sum and product(exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:

1
(accumulate combiner null-value term a next b)

Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.

b. If your accumulate procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

提取出 sum 和 product 的共同部分即可。

1
2
3
4
5
6
7
8
(define (accumulate combiner null-value term a next b)
    (if (> a b)
        null-value
        (combiner (term a)
                  (accumulate combiner null-value term (next a) next b))))

(define (product term a next b)
    (accumulate (lambda (x y) (* x y)) 1 term a next b))

迭代版

1
2
3
4
5
6
(define (accumulate combiner null-value term a next b)
    (define (iter a result)
        (if (> a b)
            result
            (iter (next a) (combiner result (term a)))))
    (iter a null-value))

习题 1.33

Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:

a. the sum of the squares of the prime numbers in the interval $a$ to $b$ (assuming that you have a prime? predicate already written)

b. the product of all the positive integers less than $n$ that are relatively prime to $n$ (i.e., all positive integers $i < n$ such that $GCD(i,n) = 1$).

先实现 filtered-accumulate

这个只需要在 accumulate 的基础上加上一个 filter 如果通过过滤则 (term a) 没有就是 null-value

1
2
3
4
5
(define (filtered-accumulate filter combiner null-value term a next b)
    (if (> a b)
        null-value
        (combiner (if (filter a) (term a) null-value)
                  (filtered-accumulate filter combiner null-value term (next a) next b))))

用 filtered-accumulate 实现 accumulate

1
2
3
(define (accumulate combiner null-value term a next b)
  	(define (no-filter x) #t)
    (filtered-accumulate no-filter combiner null-value term a next b))

再用 accumulate 实现 sum 和 product

1
2
3
4
5
6
7
(define (sum term a next b)
  	(define (plus x y) (+ x y))
  	(accumulate plus 1 term a next b))

(define (product term a next b)
  	(define (times x y) (* x y))
    (accumulate times 1 term a next b))

现在解决第一个问题，求 a 到 b 所有素数的平方和

1
2
3
4
5
(define (sum-of-square-primes primes? a b)
    (define (plus x y) (+ x y))
    (define (square x) (* x x))
    (define (inc x) (+ x 1))
  (filtered-accumulate primes? plus 0 square a inc b))

然后解决第二个问题

1
2
3
4
5
6
(define (product-of-all-positive-integer-less-than n)
    (define (relative-prime? x) (not (= 0 (remainder x n))))
    (define (times x y) (* x y))
    (define (identity x) x)
    (define (inc x) (+ x 1))
    (filtered-accumulate relative-prime? times 1 identity 0 inc n))

习题 1.34

Exercise 1.34. Suppose we define the procedure

1
2
(define (f g)
  (g 2))

Then we have

1
2
3
4
(f square)
4
(f (lambda (z) (* z (+ z 1))))
6

What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.

1
2
3
4
5
6
7
8
(f f)
; 先对一个 f 求值，返回函数
; 对第二个 f 求值，返回函数
; 应用整个列表
; 将第二个 f 当作参数传给第一个 f
(f 2)
(2 2)
; 非法调用，2 不是一个函数。

习题 1.35

Exercise 1.35. Show that the golden ratio $\phi$ (section 1.2.2) is a fixed point of the transformation $ x \rightarrow 1 + 1/x$, and use this fact to compute $\phi$ by means of the fixed-point procedure.

直接调用fixed-point即可。

1
2
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1)
; 987/610 = 1.618032786885246

习题 1.36

Exercise 1.36. Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to $x^x = 1000$ by finding a fixed point of $x \rightarrow \log{1000}/\log{x}$. (Use Scheme’s primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by $\log{1} = 0$.)

直接套用fixed-point即可。初始值不要选 $1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (/ (log 1000) (log x))) 1.1)
; 4.555538934848503

习题 1.37

Exercise 1.37. a. An infinite continued fractionis an expression of the form
$$
f = \cfrac{N_1}{D_1+\cfrac{N_2}{D_2 + \cfrac{N_3}{D_3+ …}}}
$$
As an example, one can show that the infinite continued fraction expansion with the $N_i$ and the $D_i$ all equal to 1 produces $1/\phi$ , where $\phi$ is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation – a so-called k-term finite continued fraction – has the form
$$
\cfrac{N_1}{D_1+\cfrac{N_2}{… + \cfrac{N_K}{D_K}}}
$$

Suppose that $n$ and $d$ are procedures of one argument (the term index $i$) that return the $N_i$ and $D_i$ of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating $1/\phi$ using

1
2
3
(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

for successive values of $k$. How large must you make $k$ in order to get an approximation that is accurate to 4 decimal places?

b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

先根据递推式编写连分数代码。

1
2
3
4
(define (cont-frac n d k)
    (if (<= k 1)
        (/ (n 1) (d 1))
        (/ (n k) (+ (d k) (cont-frac n d (- k 1))))))

黄金分割率的 $D_i$ 和 $N_i$ 都是 $1$ 

1
2
3
4
(define (cont-frac-golden-ratio k)
    (cont-frac (lambda (i) 1.0)
               (lambda (i) 1.0)
               k))

接着解决精度问题。

计算不同的 $k$ 当两个值的差在误差之内则是想要的结果。

1
2
3
4
5
6
7
(define tolerance 0.00001)

(define (how-much guess)
    (if (> tolerance (abs (- (cont-frac-golden-ratio guess)
                             (cont-frac-golden-ratio (+ guess 1)))))
        guess
        (how-much (+ 1 guess))))

测试

1
2
3
4
5
(how-much 1)
; 12

(cont-frac-golden-ratio 12)
; 0.6180257510729613

迭代版

1
2
3
4
5
6
(define (cont-frac n d k)
    (define (iter n d k result)
        (if (<= k 0)
            result
            (iter n d (- k 1) (/ (n k) (+ (d k) result)))))
    (iter n d k 0))

习题 1.38

Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for $e - 2$, where $e$ is the base of the natural logarithms. In this fraction, the $N_i$ are all 1, and the $D_i$ are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …. Write a program that uses your cont-frac procedure from exercise 1.37 to approximate $e$, based on Euler’s expansion.

观察 $D_i$ 可得
$$
D_i =
\begin{cases}
1, & i = 1, i \bmod 3 \ne 2
\2 \times (\lfloor i/3 \rfloor + 1), &\text{otherwise}
\end{cases}
$$
程序如下

1
2
3
4
5
6
7
8
9
10
11
(define (d i)
    (if (= i 1)
        1
        (if (= (remainder i 3) 2)
            (* 2 (+ 1 (quotient i 3)))
            1)))

(define (euler-method k)
    (+ 2 (cont-frac (lambda (i) 1.0)
                    d
                    k)))

测试

1
2
(euler-method 100)
; 2.7182818284590455

习题 1.39

Exercise 1.39. A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:
$$
\tan x = \cfrac{x}{1-\cfrac{x^2}{3-\cfrac{x^2}{5-…}}}
$$
where $x$ is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert’s formula. K specifies the number of terms to compute, as in exercise 1.37.

观察分子 $n_i$ 可得
$$
n_i =
\begin{cases}
x & i = 1
\x^2 & i \ne 1
\end{cases}
$$
$D_i$ 规律为
$$
D_i = (i - 1) \times 2 + 1
$$
仿照上面 cont-frac 的代码得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (cont-frac n d k)
    (define (iter n d k result)
        (if (<= k 0)
            result
            (iter n d (- k 1) (/ (n k) (- (d k) result)))))
    (iter n d k 0))
    
(define (tan-cf x k)
    (define (n i)
        (if (= i 1)
            x
            (* x x)))
    (define (d i) (+ 1 (* 2.0 (- i 1))))
    (cont-frac n d k))

测试

1
2
(tan-cf 1 100)
; 1.557407724654902

习题 1.40

Exercise 1.40. Define a procedure cubic that can be used together with the newtons-method procedure in expressions of the form

1
(newtons-method (cubic a b c) 1)

to approximate zeros of the cubic $x^3 + ax^2 + bx +c$ .

将多项式写成代码即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define dx 0.00001)

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))
  
(define (cubic a b c )
    (lambda (x) (+ (* x x x)
                   (* a (* x x))
                   (* b x)
                   c)))

测试

1
2
(newtons-method (cubic 1 1 (- 39)) 1.0)
; 3.00000000000019504

习题 1.41

Exercise 1.41. Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2. What value is returned by

1
(((double (double double)) inc) 5)

1
2
3
4
5
6
(define (double f)
    (lambda (x) (f (f x))))
    
(define (inc x) (+ x 1))
    
(((double (double double)) inc) 5)

分析

double(f)(x) 等于 $f(f(x))$ 也就是 $f^2(x)$

所以 (double double)(f)(x) 等于 $f^2(f^2(x))$ 也就是 $f^4(x)$

那么 (double (double double))(f)(x) 等于 $f^4(f^4(x))$ 也就是 $f^{16}(x)$

inc 应用 16 次 则为 +16 。

$ 16 + 5 = 21 $

所以答案是 21

习题 1.42

Exercise 1.42. Let $f$ and $g$ be two one-argument functions. The composition $f$ after $g$ is defined to be the function $x \rightarrow f(g(x))$ . Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument

1
2
((compose square inc) 6)
49

返回一个函数即可。

1
2
3
4
5
6
(define (compose f g)
    (lambda (x) (f (g x))))

(define (square x) (* x x))

(define (inc x) (+ x 1))

测试

1
2
((compose square inc) 6)
; 49

习题 1.43

Exercise 1.43. If $f$ is a numerical function and $n$ is a positive integer, then we can form the $n$th repeated application of $f$, which is defined to be the function whose value at $x$ is $f(f(…(f(x))…))$ . For example, if $f$ is the function $x \rightarrow x + 1$ , then the $n$th repeated application of $f$ is the function $x \rightarrow x + n$. If $f$ is the operation of squaring a number, then the $n$th repeated application of $f$ is the function that raises its argument to the $2^n$th power. Write a procedure that takes as inputs a procedure that computes $f$ and a positive integer $n$ and returns the procedure that computes the $n$th repeated application of $f$. Your procedure should be able to be used as follows:

1
2
((repeated square 2) 5)
625

Hint: You may find it convenient to use composefrom exercise 1.42.

重复应用的递推式为
$$
f^n(x) = f(f^{n-1}(x))
$$
代码如下

1
2
3
4
5
6
7
8
(define (square x) (* x x))

(define (inc x) (+ x 1))

(define (repeat f n)
    (if (<= n 1)
        f
        (compose f (repeat f (- n 1)))))

测试

1
2
3
4
((repeat inc 10) 2)
; 12
((repeat square 2) 5)
; 625

习题 1.44

Exercise 1.44. The idea of smoothing a function is an important concept in signal processing. If $f$ is a function and $dx$ is some small number, then the smoothed version of $f$ is the function whose value at a point $x$ is the average of $f(x - dx)$ ,$f(x)$, and $f(x + dx)$ . Write a procedure smooth that takes as input a procedure that computes $f$ and returns a procedure that computes the smoothed $f$. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function usingsmooth and repeated from exercise 1.43.

这个比较简单，直接按定义写代码即可。

1
2
3
4
5
6
7
8
(define (smooth f)
    (define dx 0.00001)
    (define (average x y z) (/ (+ x y z) 3))
    (lambda (x) 
        (average (f (- x dx)) (f x) (f (+ x dx)))))

(define (fold-smooth f n)
    ((repeat smooth n) f))

测试

1
2
3
4
((smooth square) 2)
; 4.000000000006667
(fold-smooth square 10) 2)
; 4.000000000666667

习题 1.45

Exercise 1.45. We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of $y \rightarrow x/y$ does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped $y \rightarrow x/y^2$ . Unfortunately, the process does not work forfourth roots – a single average damp is not enough to make a fixed-point search for $y \rightarrow x/y^3$ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of $y \rightarrow x/y^3$) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute $n$th roots as a fixed-point search based upon repeated average damping of $y \rightarrow x/y^{n-1}$. Use this to implement a simple procedure for computing $n$th roots using fixed-point, average-damp, and the repeatedprocedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

组合之前的 repeat fixed-point 和 average-damp 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (nth-root n x)
    (fixed-point ((repeat average-damp n) (lambda (y) (/ x (expt y (- n 1))))) 1.0))

经测试重复 n 次是可以的。

重复 $\frac{n}{2}$ 也是可以的。

但应该还有一个更确切的下界。需要通过数学推导得到。

习题 1.46

Exercise 1.46. Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improvethat takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improveshould return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrtprocedure of section 1.1.7 and the fixed-pointprocedure of section 1.3.3 in terms of iterative-improve.

提取出共同部分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (iterative-improve good-enough? improve)
    (define (f guess)
        (if (good-enough? guess)
            guess
            (f (improve guess))))
    f)

(define (fixed-point f first-guess)
    (define tolerance 0.00001)
    (define (good-enough? x)
        (< (abs (- x (f x))) tolerance))
    (define (improve x) (f x))
    ((iterative-improve good-enough? improve) first-guess))

(define (sqrt x)
    (define tolerance 0.001)
    (define (good-enough? guess next)
        (< (abs (- guess next)) tolerance))
    (define (improve guess)
        (average guess (/ x guess)))
    (define (average a b)
        (/ (+ a b) 2))
    ((iterative-improve good-enough? improve) 1.0))

测试

1
2
3
4
(fixed-point cos 1.0)
; 0.7390822985224024
(sqrt 9)
; 3.000000001396984