SICP Exercise 1.43: Compose... Again... and Again... and Again...

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

> ((repeated square 2) 5)
625

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

First of all, let's just clarify what we're asked for here. We're not being asked to define a procedure that can take, for example, (lambda (x) (+ x 1)) and the value n and return the procedure (lambda (x) (+ x n)). Instead we're being asked to define a procedure that returns a procedure that computes the n^th repeated application of f. I.e. it applies f n times in sequence.

We're also given a nice hint. We can use compose to do this. And we can do this with an iterative procedure. How? Well, compose allows us to combine two single-parameter procedures together to produce a procedure that is the result of applying the first to the result of the second. All we need to do is to start with f as our result, and iterate from 1..n, at each step composing the result so far with another application of f, until we reach n, at which point we'll have our desired procedure:

(define (repeated f n)
  (define (iter i result)
    (if (= i n)
        result
        (iter (+ i 1) (compose f result))))
  (iter 1 f))

Of course we can be a bit smarter about this... Back in section 1.2.4 we learned about the successive squaring approach to exponentiation. We can use a similar approach for producing the procedure that calculates the n^th repeated application of f by noting that:

• When n is even, (repeated f n) ≡ (compose ff ff), where ff is defined as (repeated f (/ n 2)).
• When n is odd, (repeated f n) ≡ (compose f (repeated f (- n 1)))

While this won't save us any steps when we're actually calculating the n^th repeated application of f to a value, it will save steps in the evaluation of repeated and the procedure produced will likely have a more compact representation. Here's the smarter version:

(define (repeated f n)
  (cond ((= n 1) f)
        ((even? n) (let ((ff (repeated f (/ n 2))))
                     (compose ff ff)))
        (else (compose f (repeated f (- n 1))))))

And to confirm this works:

> ((repeated square 2) 5)
625
> (define add10 (repeated inc 10))
> (add10 5)
15
> (add10 20)
30
> (add10 (add10 3))
23