SICP 1.45 - Почему эти две функции более высокого порядка не эквивалентны?

Question

Я выполняю упражнения в [SICP] [1] и задаюсь вопросом, может ли кто-нибудь объяснить разницу между этими двумя, казалось бы, эквивалентными функциями, которые дают разные результаты!Это из-за округления ??Я думаю, что порядок функций здесь не имеет значения, но как-то это имеет значение?Может кто-нибудь объяснить, что здесь происходит и почему все по-другому?

Детали:

Упражнение 1.45 : .. увидел, что нахождение фиксированной точки y => x/yне сходится, и что это можно исправить с помощью среднего демпфирования.Тот же метод работает для нахождения корней куба в качестве фиксированных точек среднего затухания y => x/y^2.К сожалению, этот процесс не работает для четвертых корней - одного среднего затухания недостаточно, чтобы выполнить поиск с фиксированной точкой для сходящихся y => x/y^3.

С другой стороны, если мы усредняем затухание дважды (т.е. используем среднее затухание среднего затухания y => x/y^3), поиск с фиксированной точкой действительно сходится.Проведите несколько экспериментов, чтобы определить, сколько средних затуханий требуется для вычисления n-х корней в качестве поиска с фиксированной точкой на основе повторного среднего затухания 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 влечет за собой

  ((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шаги с , один раз , с демпфированием по среднему значению (foo n) на каждом шаге итерации, выполняемом fixed-point;В сети используется шаг итерации *1025* k со средним демпфированием (foo n).Обратите внимание, что независимо от того, сколько раз он используется, функция один раз с демпфированием по среднему показателю все еще имеет среднее демпфирование только один раз , и ее использование несколько развероятно, только усугубит проблему, а не решит ее.

Для 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) в определенные y с, и чем выше k, тем сильнее эффект демпфирования, как ясно видно из последней формулы.

Answer 2

Вы спрашиваете, почему «две, казалось бы, эквивалентные функции» дают разные результаты, но эти две функции в действительности сильно различаются.

Давайте попробуем упростить задачу, чтобы понять, почему они разные.Единственное различие между этими двумя функциями заключается в двух выражениях:

(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 и более простую функцию, чем эта лямбда, например, следующая функция:

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

, что эквивалентноto:

(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

Разница в результате не из-за числового приближения, а из-за другого вычисления: first (average-damping succ) возвращает функцию h, которая вычисляет среднее значение между параметром и его преемником;затем (average-damping h) возвращает новую функцию, которая вычисляет среднее значение между параметром и результатом функции h.Такая функция, если передано число, подобное 3, сначала вычисляет среднее значение от 3 до 4, что составляет 3,5, затем вычисляет среднее значение от 3 (снова параметр) до 3,5 (предыдущий результат), получая 3,25.