高阶函数应用

用高阶函数 fixed-point 与 iterate 演示抽象实战：计算不动点、平方根与迭代改进。

笔记

本节内容比本课其他部分稍难。如果你在本节感到吃力，别担心——它比我们要求大家掌握的大部分内容都要进阶。

在这里，我们将用目前学到的工具探索两个应用实例：fixed-point 和 iterate。

`fixed-point`

我们先来尝试表达函数不动点（fixed point）的计算。如果一个数 x 满足方程 $f(x) = x$ ，就称 x 是函数 f 的一个不动点。

对某些函数 f 寻找不动点的算法是这样的：从一个初始猜测值出发，反复应用 f，直到相继得到的值非常接近。

x
(f x)
(f (f x))
...

顺着这个思路，我们来编写一个过程 fixed-point：不断应用某个函数，直到找到两个相继的值，其差值小于某个规定的容差（tolerance）。看看我们对 fixed-point 的定义：

(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))

例如，我们可以用这个方法近似余弦函数的不动点，初始近似值取 1：

-> (fixed-point cos 1.0)
0.7390822985224024

为了展示用 fixed-point 抽象函数的威力，我们将只用 3 行 Racket 代码开发出一种计算平方根的方法！

计算某个数 x 的平方根，就是要找到一个 y 使得 $y^2 = x$ 。把这个方程改写成等价形式 $y = x / y$ ，你会发现我们要找的就是函数 (lambda (y) (/ x y)) 的不动点。写成代码：

(define (sqrt x)
    (fixed-point (lambda (y) (/ x y))
    1.0))

不过，如果你手边有解释器，你会发现这样行不通。看看以 (sqrt 4) 为例的一系列猜测值就知道了：

1
4/1 = 4
4/4 = 1
4/1 = 4
...

它一直在振荡！仔细想想，你会发现除了 0 和 1，我们输入任何数都会这样。

所以，我们不让猜测值一步变为新值，而是稍微调整得小一些。具体做法是：把下一次猜测值与当前猜测值取平均。也就是说，y 之后的下一个猜测值是 $\frac{1}{2}(y + x/y)$ ，而不是 $x/y$ 。

产生这样一系列猜测值的过程，本质上就是在寻找 $y = \frac{1}{2}(y + x/y)$ 的不动点的过程：

(define (sqrt x)
    (fixed-point (lambda (y) (* 0.5 (+ y (/ x y))))
    1.0))

经过这样的修改，平方根过程就能正常工作了。这种对相继近似值取平均的做法——SICP 的作者称之为平均阻尼（average damping）——常常有助于不动点搜索的收敛。

那么，让我们继续抽象狂热，把平均阻尼技术也抽象出来：

(define (average-damp f)  
     (lambda (y) (* 0.5 (+ y (f y)))))

于是有了新的 sqrt：

(define (sqrt x)  
  (fixed-point (average-damp (lambda (y) (/ x y)))  
               1.0))

清晰得惊人，不是吗？

笔记

$y = \frac{1}{2}(y + x/y)$ 是方程 $y = x / y$ 的一个简单变换；要推导它，在方程两边同时加上 y，再除以 2。

你可能已经注意到，我们实际上推导出了计算平方根的牛顿法（Newton’s method）。但是……方法还有很多！如果你感兴趣，这里有一个很棒的链接。

`iterate`

我们将用另一个高阶函数来结束本课。

这个函数能让我们同时写出 fixed-point 和第 1 课的 largest-square。

怎么做到的呢？因为它们都属于迭代改进（iterative improvement）的一般形式：从一个值出发，不断改进它，直到它足够好。

注意，这里有 3 样东西需要抽象：

起始值；
用于改进的函数；
用于检验是否足够好的函数。

这样一来，我们就知道了形参和它该做的事，动手写吧！

(define (iterate start improve good-enough?)  
   (if (good-enough? start)  
       start  
       (iterate (improve start) improve good-enough?)))

现在，我用 iterate 来表达 largest-square：

(define (largest-square total guess)  
    (iterate guess   
             (lambda (x) (+ x 1))  
             (lambda (x) (< total (square (+ x 1))))  
     ))

我们的抽象狂热（基本上）到此为止，但请保持警觉。正是抽象让程序员能够写出复杂而又可读的系统。

永远不要错过任何一个抽象的好机会。