SICP exercise 1.43

From Drewiki

Problem

If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is . For example, if f is the function , then the nth repeated application of f is the function . If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2ⁿth power. 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. Your procedure should be able to be used as follows:

((repeated square 2) 5)

which should evaluate to 625.

Hint: You may find it convenient to use compose from exercise 1.42.

Solution

We know that repeated must ultimately return a lambda function of one argument. Here's an iterative implementation of procedure repeated. It builds the requested function by repeatedly composing its function argument, f, with the cumulative composition of previous iterations. The iteration is seeded with f itself.

(define (compose f g)
  (lambda (x) (f (g x))))
 
(define (inc x) (+ x 1))
 
(define (repeated f n)
  (define (repeated-iter i result)
    (if (= i n)
        result
        (repeated-iter (inc i) (compose f result))))
  (repeated-iter 1 f))

Test:

(define (square x) (* x x))
 
((repeated square 2) 5)

Output:

625

((repeated inc 3) 7)

Output:

10