Решение упражнения 1.44 из SICP

4 November, 2007 (19:07) | Решения упражнений

Это просто замечательнейшее упражнение! Сейчас объясню, почему оно мне так понравилось, но начнем с простого, то есть с определения процедуры smooth. Здесь все достаточно легко:

(define (smooth f dx)
  (define (average x y z) (/ (+ x y z) 3))
  (lambda (x) (average (f (- x dx))
                       (f x)
                       (f (+ x dx)))))

А вот теперь часть похитрее – многократное сглаживание. Приведу первое решение, которое пришло мне в голову:

(define (smooth-n f dx n)
  (repeated (smooth f dx) n))

Оно хорошо краткостью своей записи, но неверно по сути. Правильное же решение записывается следующим образом:

(define (smooth-n f dx n)
  ((repeated (lambda (g) (smooth g dx)) n) f))

В чем разница (помимо более длинной записи)? Давайте разберемся.

Может показаться, что эти две записи эквивалентны, но это не так. Отличие в вызове процедуры smooth:

(smooth f dx) против (lambda (g) (smooth g dx))

Я хочу подчеркнуть, что (smooth f dx) – это процедура, которая принимает число и возвращает число. А вот (lambda (g) (smooth g dx)) – это процедура, которая принимает процедуру одного числового аргумента и возвращает также процедуру одного числового аргумента. Прочувствуйте отличие:

  • число на входе и число на выходе;
  • процедура на входе и процедура на выходе.

Прочитаем первый вариант реализации: применяем однократно сглаженную функцию f последовательно n раз к своему же результату (то есть функцию f'(f'(…f'(x)…)), где f’ – это сглаженная f); получаем функцию числового аргумента. То, что надо? Не похоже…

Второй вариант реализации smooth-n читается таким образом: к функции f применяем преобразование, получающееся в результате применения сглаживания n раз; в результате получаем функцию числового аргумента. Оно? Оно!

Это может показаться не очень простым в понимании. Рекомендую в таком случае попробовать вычислить

((smooth-n square 0.5 2) 1.0)

вручную и программно двумя способами и осознать, почему результаты двух описанных выше процедур smooth-n различны. И добро пожаловать в комментарии.

Comments

Comment from Sergey Khenkin
Date: January 12, 2008, 2:00 pm

Если превратить определение dx из параметра процедур smooth и smooth-n в константу, то код существенно упростится и примет такой вид:

(define (smooth-n f n)
  ((repeated smooth n) f))

Comment from vladimir
Date: November 8, 2011, 7:10 am

ошибка из за невнимательности и долгие часы мучений.
спасибо за сайт, а то еще долго бы думал 🙂

Comment from spec
Date: February 11, 2013, 1:36 pm

Напишите процедуру smooth, которая в качестве ввода принимает процедуру, вычисляющую f, и возвращает процедуру, вычисляющую сглаженную версию f.

У вас же dx залез)

Comment from Ilyas
Date: December 11, 2015, 12:30 am

(define (smooth f)
  (define (average x y z)
    (/ (+ x y z) 3))
  (lambda (x) (average (f (- x dx)) (f x) (f (+ x dx)))))
(define (repetead-smooth f n x)
  (((repeated smooth n) f) x))

Правильно ли я сделал?

Comment from Irv
Date: January 13, 2016, 3:05 pm

повторил путь автора

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

(define (repeat f times)
  (define (iter i g)
    (if (= i times)
        g
        (iter (+ 1 i) (compose f g))))
  (iter 1 f))

(define (smooth f)
  (let ((dx 0.0001))
    (lambda(x) (/
                (+
                 (- (f x) dx)
                 (f x)
                 (+ (f x) dx))
                3))))

;(smooth (smooth (smooth (f x)))

(define (n-smooth f n)
  ((repeat smooth n) f))

Comment from Алексей
Date: August 12, 2017, 7:13 pm

Может это из-за новой версии интерпретатора, но у меня оба варианта идентичны. Всё копировал у автора и проверял.

Write a comment