<< Previous exercise (1.42) | sicp-solutions | Next exercise (1.44) >>
Define some primitives:
(define (square x) (* x x)) (define (compose f g) (lambda (x) (f (g x))))
Define the procedure:
(define (repeat f n) (if (< n 1) (lambda (x) x) (compose f (repeat f (- n 1)))))
((repeat square 2) 5)
Another solution using the linear iterative way.
(define (repeat f n) (define (iter n result) (if (< n 1) result (iter (- n 1) (compose f result)))) (iter n identity))
Note: This is not linearly iterative as described in the book as a chain of deferred operations is still being built.
The above answer does not follow the book's instructions. The book instructs "Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f." A correct answer is as follows:
(define (repeated f n) (lambda (x) (cond ((= n 0) x) (else ((compose (repeated f (- n 1)) f) x)))))
I think the following solution is more elegant. When we only need to apply the function once, we can just return the function (I'm not doing error-checking here to see of n is smaller than 1).
(define (repeated f n) (if (= n 1) f (compose f (repeated f (- n 1)))))
An extremely succinct solution uses the accumulate procedure defined in 1.32:
(define (repeated f n) (accumulate compose identity (lambda (i) f) 1 inc n))
An solution with O(log n) complexity using compose:
(define (repeated f n) (cond ((= n 0) identity) ((even? n) (repeated (compose f f) (/ n 2))) (else (compose f (repeated f (- n 1))))))
A logarithmic iterative solution.
(define (lcompose f g) (lambda (x) (g (f x)))) (define (identity x) x) (define (repeated f n) (define (iter g h m) (cond ((= m 0) g) ((odd? m) (iter (lcompose g h) h (- m 1))) (else (iter g (lcompose h h) (/ m 2))))) (iter identity f n))
I personally would rather like to avoid using compose (as the only actual use I see in it would be in the logarithmic solution given above).
(define (repeated f n) (define (repeated-step counter input) (if (> counter n) input (f (repeated-step (+ counter 1) input)) ) ) (lambda (x) (repeated-step 1 x)) )