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

1 November, 2007 (21:16) | Решения упражнений

Интересное упражнение. Да и вообще работа с функциями высших порядков – сплошное интеллектуальное удовольствие. Процедура double записывается очень просто:

(define (double f) 
  (lambda (x) (f (f x))))

Ее запуск в простых случаях приводит ко вполне ожидаемым результатам:

> ((double square) 2) 
16
> ((double inc) 5) 
7

Что же выведет (((double (double double)) inc) 5)? В этом случае выводится число 21. Почему? Все достаточно просто.

Если вызов double вызывает функцию дважды, то запись (double double) означает функцию, которая принимает один аргумент – функцию одного параметра и вызывает ее четырежды. Тут неожиданностей нет. Более странным может показаться то, что ((double (double double)) вызывает свой аргумент не 8 раз, как могло бы показаться, а 16. Дело в том, что двойной вызов функции означает композицию функции с собой же, то есть функция-аргумент вызывается четыре раза по четырежды, то есть 16 раз. В итоге, инкрементируя число 5 шестнадцать раз, получаем 21.

Comments

Comment from Максим
Date: November 16, 2014, 8:08 pm

Сергей скажите, а как получить ответ используя substitution model? Не понимаю в какой момент в оператор (double (double double)) встраивается функция операнд inc, когда эти дубли раскрываются в кучу ((f(f(x)) (f(f(x)…

Write a comment