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

2 November, 2007 (20:50) | Решения упражнений

Продолжим наше жонглирование пудовыми функциями с той же легкостью, с которой обычно управляются с подобными перышкам примитивными переменными. Воспользовавшись подсказкой об использовании ранее написанной процедуры compose и заметив, что повторенная n раз функция f – это композиция повторенной n-1 раз функции f с самой функцией f, легко получим такой код процедуры:

(define (repeated f n) 
  (if (> n 1) 
      (lambda (x) ((compose (repeated f (- n 1)) f) x)) 
      f))

Результаты вычисления оказываются ожидаемыми:

> ((repeated square 2) 5) 
625 
> ((repeated inc 3) 5) 
8

Никаких неожиданностей.

Comments

Comment from Sergey Khenkin
Date: November 4, 2007, 8:11 pm

Пример реализации repeated, порождающей итеративный процесс, можно подглядеть у Кена Дика – http://www.kendyck.com/archives/2007/06/04/solution-to-sicp-exercise-143/

Comment from SiGMan
Date: January 5, 2008, 10:13 am

По-моему тут есть кое-что лишее, лучше так:

(define (apply-ntimes-simple f n)
  (if (> n 1)
      (compose (apply-ntimes-simple f (- n 1)) f)
      f ))

Comment from Sergey Khenkin
Date: January 6, 2008, 2:28 pm

Да, согласен, тут я перемудрил немножко. Проще нужно быть :)

[не по теме] Ник SiGMan имеет какое-то отношение к http://sigman.cs.umn.edu/ ?

Comment from gorilych
Date: July 16, 2008, 8:37 am

а так? (accumulate итеративна)

(define (repeated f n)
  (accumulate compose identity (lambda (i) f) 1 inc n))

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

В книге есть глава, в ней говорится что самое клевое, когда видны абстракции и алгоритм.
А то что у вас lambda знает о процедуре вызывающей ее вообще бяка.

(define (repeated_r f n)
  (lambda (x) 
    (define ( inner f n) 
      (if ( = n 1)
       (f x)
       (f ( inner f (- n 1)))
      )
    )
    ( inner f n) 
   )
 )

Comment from shini
Date: August 8, 2013, 11:24 pm

2 часа сидел, думал,думал, не додумал.Сдался.

Comment from shini
Date: August 8, 2013, 11:24 pm

2 часа сидел, думал,думал, не додумал.Сдался…

Comment from alexk
Date: July 31, 2014, 10:29 pm

(define (repeated f c)
  (define (iter i res)
    (if (= i c) res (iter (inc i) (compose f res)))
    )
  (iter 0 identity)
  )

Comment from Sergk
Date: December 10, 2014, 9:06 am

Мой вариант, думаю тоже правильный, но не совсем попал в суть упражнения

(define (repeated f g)
  (lambda (x) (if (= g 1)
                    (f x)
                    (f ((repeated f (- g 1)) x)))))

Comment from Irv
Date: January 11, 2016, 6:30 pm

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

((repeat (lambda (x) (* x x)) 2) 5)

Write a comment