scheme - SICP 1.45 - 为什么这两个高阶函数不等价？

Question

我正在完成 [SICP][1] 中的练习，想知道是否有人可以解释这两个看似等效但结果不同的函数之间的区别!这是因为四舍五入吗？？我认为函数的顺序在这里不重要，但不知何故呢？有人可以解释这里发生了什么以及为什么不同吗？

详细信息:

Exercise 1.45: ..saw that finding a fixed point of y => 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 => x/y^2. Unfortunately, the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for y => 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 => x/y^3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of y => x/y^(n-1).

Use this to implement a simple procedure for computing the roots using fixed-point, average-damp, and the repeated procedure of Exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

我的答案(注意 repeat 和 average-damping 的顺序):

(define (nth-root-me x n num-repetitions)
  (fixed-point (repeat (average-damping (lambda (y)
                                           (/ x (expt y (- n 1)))))
                       num-repetitions)
               1.0))

我看到一个替代的网络解决方案，其中 repeat 直接在 average damp 上调用，然后使用参数调用该函数

(define (nth-root-web-solution x n num-repetitions)
      (fixed-point
         ((repeat average-damping num-repetition)
          (lambda (y) (/ x (expt y (- n 1)))))
         1.0))

现在调用这两个，答案似乎有所不同，我不明白为什么!我的理解是函数的顺序不应该影响输出(它们是关联的，对吗？)，但显然它是!

> (nth-root-me 10000 4 2)
> 
> 10.050110705350287
> 
> (nth-root-web-solution 10000 4 2)
> 
> 10.0

我做了更多的测试，它总是这样，我的答案很接近，但另一个答案几乎总是更接近!有人可以解释发生了什么吗？为什么这些不等价？我的猜测是调用这些函数的顺序弄乱了它，但它们对我来说似乎是关联的。

例如:

(repeat (average-damping (lambda (y) (/ x (expt y (- n 1)))))
         num-repetitions)

对比

((repeat average-damping num-repetition)
 (lambda (y) (/ x (expt y (- n 1)))))

其他辅助函数:

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2))
       tolerance))
  (let ((next-guess (f first-guess)))
    (if (close-enough? next-guess first-guess)
        next-guess
        (fixed-point f next-guess))))

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

(define (repeat f k)
  (define (repeat-helper f k acc)
    (if (<= k 1)
        acc
           ;; compose the original function with the modified one
        (repeat-helper f (- k 1) (compose f acc)))) 
  (repeat-helper f k f))

(define (compose f g)
  (lambda (x)
    (f (g x))))

Answer 1

您问的是为什么“两个看似等价的函数”会产生不同的结果，但实际上这两个函数却截然不同。

让我们尝试简化问题，看看它们为何不同。这两个函数之间的唯一区别是两个表达式:

(repeat (average-damping (lambda (y) (/ x (expt y (- n 1)))))
        num-repetitions)

((repeat average-damping num-repetition)
   (lambda (y) (/ x (expt y (- n 1)))))

为了简化我们的讨论，我们假设 num-repetition 等于 2，并且有一个比 lambda 更简单的函数，例如以下函数:

(define (succ x) (+ x 1))

所以现在两个不同的部分是:

(repeat (average-damping succ) 2)

和

((repeat average-damping 2) succ)

现在，对于第一个表达式，(average-damping succ) 返回一个numeric 函数，该函数计算参数与其后继参数之间的平均值:

(define h (average-damping succ))
(h 3) ; => (3 + succ(3))/2 = (3 + 4)/2 = 3.5

因此，表达式 (repeat (average-damping succ) 2) 等价于:

(lambda (x) ((compose h h) x)

相当于:

(lambda (x) (h (h x))

同样，这是一个数字函数，如果我们将这个函数应用到 3，我们有:

((lambda (x) (h (h x)) 3) ; => (h 3.5) => (3.5 + 4.5)/2 = 4

在第二种情况下，我们有 (repeat average-damping 2) 产生完全不同的函数:

(lambda (x) ((compose average-damping average-damping) x)

相当于:

(lambda (x) (average-damping (average-damping x)))

你可以看到这次的结果是一个高级函数，而不是一个整数函数，它接受一个函数x并应用两次 average-damping 功能。让我们通过将此函数应用于 succ 然后将结果应用于数字 3 来验证这一点:

(define g ((lambda (x) (average-damping (average-damping x))) succ))
(g 3) ; => 3.25

结果的差异不是由于数值近似，而是由于不同的计算:首先 (average-damping succ) 返回函数 h，它计算参数与其后继参数之间的平均值；然后 (average-damping h) 返回一个新函数，该函数计算参数和函数 h 的结果之间的平均值。这样的函数，如果传递一个像 3 这样的数字，首先计算 3 和 4 之间的平均值，即 3.5，然后计算 3(再次是参数)和 3.5(之前的结果)之间的平均值，产生 3.25。