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

Question

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

细节：

练习 1.45 : ..看到找到 的不动点y => x/y不收敛，这可以通过平均阻尼来解决。相同的方法适用于寻找立方根作为 average-damped 的不动点y => x/y^2。不幸的是，该过程不适用于四次根——单个平均阻尼不足以进行定点搜索y => x/y^3以求收敛。

另一方面，如果我们两次平均阻尼（即，使用 的平均阻尼的平均阻尼 y => x/y^3），定点搜索确实收敛。做一些实验来确定需要多少平均阻尼来计算 nth 根作为基于重复平均阻尼的定点搜索y => x/y^(n-1)。

使用此实现计算使用根一个简单的过程fixed-point，average-damp和repeated锻炼的过程1.43。假设您需要的任何算术运算都可用作原语。

我的回答（注意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)返回一个数值函数，用于计算参数与其后继参数之间的平均值：

(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 然后将结果应用于数字 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。