SICP 1.45 - 为什么这两个高阶函数不等价？
SICP 1.45 - Why are these two higher order functions not equivalent?
我正在完成 [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))))
你在问为什么“两个看似等价的函数”会产生不同的结果，但实际上这两个函数却大不相同。
让我们尝试简化问题，看看它们为何不同。两个函数之间的唯一区别是两个表达式：
(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) returns 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))
同样，这是一个 numeric 函数，如果我们将此函数应用于 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) returns 函数 h，它计算参数和参数之间的平均值它的继任者；然后 (average-damping h) returns 一个新函数，计算参数和函数结果之间的平均值 h。这样一个函数，如果传递一个数字，比如 3，首先计算 3 和 4 之间的平均值，即 3.5，然后计算 3（再次是参数）和 3.5（之前的结果）之间的平均值，产生 3.25.
repeat 的定义包含
((repeat f k) x) = (f (f (f (... (f x) ...))))
; 1 2 3 k
总共 k 次嵌套调用 f。让我们把它写成
= ((f^k) x)
并定义
(define (foo n) (lambda (y) (/ x (expt y (- n 1)))))
; ((foo n) y) = (/ x (expt y (- n 1)))
然后我们有
(nth-root-you x n k) = (fixed-point ((average-damping (foo n))^k) 1.0)
(nth-root-web x n k) = (fixed-point ((average-damping^k) (foo n)) 1.0)
因此您的版本在每个 k 步上使用 once-average-damped (foo n) 函数fixed-point执行的迭代步骤；网络使用 k-times-average-damped (foo n) 作为 its 迭代步骤。请注意，无论使用多少次，一次-平均阻尼函数仍然仅一次平均阻尼，并使用它几次 可能只会加剧问题，而不是解决问题。
对于k == 1，这两个结果迭代步函数当然是等价的。
你的情况k == 2，等等
(your-step y) = ((average-damping (foo n))
((average-damping (foo n)) y)) ; and,
(web-step y) = ((average-damping (average-damping (foo n))) y)
自从
((average-damping f) y) = (average y (f y))
我们有
(your-step y) = ((average-damping (foo n))
(average y ((foo n) y)))
= (let ((z (average y ((foo n) y))))
(average z ((foo n) z)))
(web-step y) = (average y ((average-damping (foo n)) y))
= (average y (average y ((foo n) y)))
= (+ (* 0.5 y) (* 0.5 (average y ((foo n) y))))
= (+ (* 0.75 y) (* 0.25 ((foo n) y)))
;; and in general:
;; = (2^k-1)/2^k * y + 1/2^k * ((foo n) y)
区别很明显。平均阻尼用于抑制(foo n)在某些ys可能出现的不稳定跳跃，并且k越高阻尼效果越强，从上一个公式可以清楚地看出。
我正在完成 [SICP][1] 中的练习，想知道是否有人可以解释这两个看似等效但结果不同的函数之间的区别！这是因为四舍五入吗？？我认为函数的顺序在这里不重要，但不知何故呢？有人可以解释这里发生了什么以及为什么不同吗？
详情：
Exercise 1.45: ..saw that finding a fixed point of
y => x/ydoes 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-dampedy => 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 fory => x/y^3converge.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 ofy => x/y^(n-1).Use this to implement a simple procedure for computing the roots using
fixed-point,average-damp, and therepeatedprocedure 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))))
你在问为什么“两个看似等价的函数”会产生不同的结果，但实际上这两个函数却大不相同。
让我们尝试简化问题，看看它们为何不同。两个函数之间的唯一区别是两个表达式：
(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) returns 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))
同样，这是一个 numeric 函数，如果我们将此函数应用于 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) returns 函数 h，它计算参数和参数之间的平均值它的继任者；然后 (average-damping h) returns 一个新函数，计算参数和函数结果之间的平均值 h。这样一个函数，如果传递一个数字，比如 3，首先计算 3 和 4 之间的平均值，即 3.5，然后计算 3（再次是参数）和 3.5（之前的结果）之间的平均值，产生 3.25.
repeat 的定义包含
((repeat f k) x) = (f (f (f (... (f x) ...))))
; 1 2 3 k
总共 k 次嵌套调用 f。让我们把它写成
= ((f^k) x)
并定义
(define (foo n) (lambda (y) (/ x (expt y (- n 1)))))
; ((foo n) y) = (/ x (expt y (- n 1)))
然后我们有
(nth-root-you x n k) = (fixed-point ((average-damping (foo n))^k) 1.0)
(nth-root-web x n k) = (fixed-point ((average-damping^k) (foo n)) 1.0)
因此您的版本在每个 k 步上使用 once-average-damped (foo n) 函数fixed-point执行的迭代步骤；网络使用 k-times-average-damped (foo n) 作为 its 迭代步骤。请注意，无论使用多少次，一次-平均阻尼函数仍然仅一次平均阻尼，并使用它几次 可能只会加剧问题，而不是解决问题。
对于k == 1，这两个结果迭代步函数当然是等价的。
你的情况k == 2，等等
(your-step y) = ((average-damping (foo n))
((average-damping (foo n)) y)) ; and,
(web-step y) = ((average-damping (average-damping (foo n))) y)
自从
((average-damping f) y) = (average y (f y))
我们有
(your-step y) = ((average-damping (foo n))
(average y ((foo n) y)))
= (let ((z (average y ((foo n) y))))
(average z ((foo n) z)))
(web-step y) = (average y ((average-damping (foo n)) y))
= (average y (average y ((foo n) y)))
= (+ (* 0.5 y) (* 0.5 (average y ((foo n) y))))
= (+ (* 0.75 y) (* 0.25 ((foo n) y)))
;; and in general:
;; = (2^k-1)/2^k * y + 1/2^k * ((foo n) y)
区别很明显。平均阻尼用于抑制(foo n)在某些ys可能出现的不稳定跳跃，并且k越高阻尼效果越强，从上一个公式可以清楚地看出。