SICP——高阶函数做抽象

发表于 | 分类于

范围

第一章 构造过程抽象

1.3 节，用高阶函数做抽象。P37 - 48

keywords：过程作为参数、lambda 演算子

笔记

1.3.1 过程作为参数

我们可以用 define 对一些过程做抽象。例如下面这个求立方：

1
2
3
4
5
6
(* 3 3 3)
(* y y y)

抽象为：

(define (cube x) (* x x x))

这一章我们将看见一种更高级的过程抽象。通过 define 产生的过程，迫使我们永远只能使用特定的操作，并且要传入参数，而不能基于更高级的操作去工作。

如果过程只能限制以数为参数，将严重限制我们建立抽象的能力。因此我们要构造出以过程为参数、返回过程的高阶过程，以及 lambda 演算子等技巧。这是强有力的抽象机制，极大的增强了语言的表述能力。下面看看如何将过程作为参数。

考虑几个计算过程：

在这里可以明显的看出，三个过程中有一种共享的基础模式。（在一段范围内把某种东西累加起来）我们也希望程序语言足够强大，写出一个过程，表达求和的概念，而不是只能写出一种特定的求和过程。其实就上述三个过程，我们可以从中抽象出一种通式：

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

sum除了原有的两个参数 a 与 b，增加了过程参数term和next，可以很简单的看出：term是指对当前数进行一个操作后，再把结果累加。next就是计算下一步的 a 值。

下面是对原有的代码进行改进的过程，将过程作为了参数。将一个迭代累加的过程抽象成了一个通式，只需要传入过程来控制我们想要的累加形式即可。“抽象”不仅是用 sum-integers、sum-pi 等名字去描述那些过程，还可以从各种 sum 中抽象出更强的抽象：求和的概念。厉害厉害！值得一提的是，之前还很轻易地用 C 语言就可以改写的 Scheme 程序，从这里开始就变得难了。因为 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
(define (inc n)(+ n 1)) 
;定义 inc 过程，用作 x++ 的功能

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)(sum term (next a)next b)))) 

(define (sum-cubes a b)
  (sum cube a inc b)) 

(define (cube x)(* x x x)) 

(sum-cubes 1 10)
;Value: 3025

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

;这个式子会收敛于 π/8

(* 8 (pi-sum 1 1000))
;Value: 3.139592655589783

一旦有了 sum ，我们就能用它作为基本构件，去形式化其他概念。例如，求函数 f 在范围 a 和 b 之间的定积分近似值，可以用下面公式去完成：

$$\int_a^b = \lbrace f(a+\frac{dx}{2}) + f(a+dx+\frac{dx}{2}) + f(a+2dx+\frac{dx}{2}) + … \rbrace dx $$

这个式子的意思：将 x 轴取极小的小块（dx），大括号内的东西是所有长方体的长的累加，乘以 dx 就是积分。利用前面的 sum，我们可以直接描述 integral 过程：

1
2
3
4
5
6
7
(define (integral f a b dx)
  (define (add-dx x)(+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b) dx))
;Value: integral

(integral cube 0 1 0.001)
;Value: .249999875000001

1.3.2 lambda 构造

在用过程做为参数时，我们不免要定义一些诸如 pi-next、add-dx 这样的过程名。这种做法有些不舒服，这些过程用作高阶函数的参数，它们在 pi-sum 和 integral 过程之外，是没什么用途的。我们可以通过引入一种 lambda λ 表达式来完成这种描述。

1
2
;比如 pi-sum 可以这么写：
(lambda (x) (+ x 4))

lambda 创建过程的语法和 define 是一样的，只不过 lambda 不为过程提供一个名字。

可以以如下方法来阅读 lambda 语句：