练习 1.46

题目要求我们给出这样一个 iterative-improve 函数：它接受一个用于检测猜测值是否足够好的函数(close-enough?)，以及一个用于改进猜测值的函数(improve)，并返回一个接受单个初始猜测值(first-guess)的过程，这个过程可以一直改进猜测值，直到猜测足够好。

根据描述，可以给出以下形式的函数：

(define (iterative-improve close-enough? improve)
    (lambda (first-guess)
        ; ...
    ))

这个过程和 46 页的 fixed-point 非常的相似：

;;; p46-fixed-point.scm

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

fixed-point 函数不仅仅和 iterative-improve 非常相似，事实上， iterative-improve 就隐藏在 fixed-point 当中！

在 fixed-point 中， close-enough? 负责检查猜测是否足够好，而函数 f 负责改进猜测，如果我们将 close-enough? 函数抽取出来，成为额外的参数，那么 fixed-point 的定义就变成了：

(define (fixed-point f first-guess close-enough?)
    (define (try guess)
        (let ((next (f guess)))
            (if (close-enough? guess next)
                next
                (try next))))
    (try first-guess))

(define (close-enough? v1 v2)
        (< (abs (- v1 v2)) tolerance))

(define tolerance 0.00001)

如果再将 first-guess 从 fixed-point 函数的参数列表中移走，变成另一个包裹 try 函数的 lambda 的参数， fixed-point 函数的定义就变成了这样：

(define (fixed-point f close-enough?)
    (lambda (first-guess)
        (define (try guess)
            (let ((next (f guess)))
                (if (close-enough? guess next)
                    next
                    (try next))))
        (try first-guess)))

(define (close-enough? v1 v2)
        (< (abs (- v1 v2)) tolerance))

(define tolerance 0.00001)

可以看到，现在的 first-point 定义已经和前面给出的 iterative-improve 形式一样了，如果将 fixed-point 函数改名成 iterative-improve ，将参数 f 改名成 improve ，并且删除 close-enough 函数和 dx 变量，题目要求的 iterative-improve 就（神奇地）显出庐山真面目了：

;;; 46-iterative-improve.scm

(define (iterative-improve close-enough? improve)
    (lambda (first-guess)
        (define (try guess)
            (let ((next (improve guess)))
                (if (close-enough? guess next)
                    next
                    (try next))))
        (try first-guess)))

注意我们是如何一步步地从 fixed-point 函数中抽象出 iterative-improve 函数的，将这两个函数放在一起对比将是一个非常有趣的练习。

用 iterative-improve 重定义 fixed-point

;;; 46-fixed-point.scm

(load "46-iterative-improve.scm")

(define (fixed-point f first-guess)
    (define tolerance 0.00001)
    (define (close-enough? v1 v2)
        (< (abs (- v1 v2)) tolerance))
    (define (improve guess)
        (f guess))
    ((iterative-improve close-enough? improve) first-guess))

测试：

1 ]=> (load "46-fixed-point.scm")

;Loading "46-fixed-point.scm"...
;  Loading "46-iterative-improve.scm"... done
;... done
;Value: fixed-point

1 ]=> (fixed-point cos 1.0)

;Value: .7390822985224024

用 iterative-improve 重定义 sqrt

;;; 46-sqrt.scm

(load "46-iterative-improve.scm")

(define (sqrt x)
    (define dx 0.00001)
    (define (close-enough? v1 v2)
        (< (abs (- v1 v2)) dx))
    (define (improve guess)
        (average guess (/ x guess)))
    (define (average x y)
        (/ (+ x y) 2))
    ((iterative-improve close-enough? improve) 1.0))

测试：

1 ]=> (load "46-sqrt.scm")

;Loading "46-sqrt.scm"...
;  Loading "46-iterative-improve.scm"... done
;... done
;Value: sqrt

1 ]=> (sqrt 9)

;Value: 3.

讨论

blog comments powered by Disqus