高阶函数：过程作为实参

高阶函数（higher-order function，简称 HOF）是满足以下条件之一的函数：

• 接受一个函数作为实参；
• 返回一个函数作为输出。

在正式开始之前，我们先快速复习一下。

重温替换模型

你应该已经很熟悉像这样的函数定义了：

(define (f x)
  (plus1 x)

在这个函数定义中，f 的形参（parameter）是 x，它作为实参被传入内置过程 plus1 的主体。如果调用我们在第 1 课学过的替换模型，可以说对 f 的一次调用（比如 (f 5)）会按以下步骤求值：

-> (f 5)
-> (plus1 5)
6

实参 5 被替换进 f 的主体，我们再对 5 调用 plus1，得到 6。好吧，这太简单了。但如果我们在主体中不把 x 用作函数的实参，而是把它本身当作函数来用，会发生什么呢？

一个简单的高阶函数

看一个例子。

(define (f g)
  (g 2))

你看到 g 出现在运算符（operator）位置了吗？嗯，有意思。如果我们这次调用 (f 5)，会发生什么？

-> (f 5)
-> (5 2)
; application: not a procedure;
;  expected a procedure that can be applied to arguments
;   given: 5
; [,bt for context]

哎呀，看来我们需要传给 f 的是一个过程，而不是数字。

-> (f square)
-> (square 2)
4

我们也可以给 f 传入一个 lambda 函数！

-> (f (lambda (x) (* x x)))
-> ((lambda (x) (* x x)) 2)
-> (* 2 2)
-> 4

你看到了吗！我们刚刚定义了函数 f，它接受一个过程 g 作为实参，并把 g 应用到 2 上。这就是你的第一个高阶函数。动手玩玩，看看你能不能自己定义出接受其他过程作为实参的过程。

把函数作为实参传入的用途

既然我们已经看到函数可以被传来传去，那就来实际探索一下这有什么用处。

看看下面这三个函数：

(define (sum-doubles a b)
  (if (> a b)
      0
      (+ (* 2 a) (sum-doubles (+ a 1) b))))

(define (sum-squares a b)
  (if (> a b)
      0
      (+ (square a) (sum-squares (+ a 1) b))))

(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

这三个函数分别计算 a 到 b 之间所有整数的翻倍值、平方值、立方值之和。

例如，(sum-squares 5 8) 计算 $5^2 + 6^2 + 7^2 + 8^2$。

把这三个函数都定义一遍似乎有些冗余。你有没有看出来，除了代码中带下划线的部分之外，这三个函数的定义几乎一模一样？是时候做一些抽象（abstraction）了。

我们知道，对于这三个函数中的每一个，我们都要对 a 到 b 之间的每个元素应用某个运算。所以，与其为每种运算写一个专用函数，不如把运算抽象出来，放进函数的形参里！

这样，我们就不需要为每一种可能的运算都写一个专用的 sum-[op] 函数，只需要一个通用的函数 sum：

(define (sum fn a b)
  (if (> a b)
      0
      (+ (fn a) (sum fn (+ a 1) b))))

我们在上面用下划线标出了代码中主要的差异之处。在 sum 的这个定义中，如你在递归调用里所见，我们把某个输入函数 fn 应用到 a 到 b 之间的每个数上。

现在，我们可以这样写：

(sum (lambda (x) (* 2 x)) 5 8)

也可以这样写：

(sum square 5 8)

还可以这样写：

(sum cube 5 8)

只写了一个过程 sum，我们就获得了上面三个过程的全部功能。多划算的买卖！

如果你愿意，最初那三个过程可以用 sum 重新定义如下：

(define (sum-squares a b)
  (sum square a b))

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

(define (sum-doubles a b)
  (sum (lambda (x) (* 2 x)) a b))

在课后作业中，我们将借助一个极其有用且广为人知的高阶函数 accumulate，把 sum 的抽象再推进一步。务必理解 accumulate 的工作原理，因为你在以后的练习中会用到它！