Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.43

From Drewiki
Jump to: navigation, search

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 <math>f(f(\cdots(f(x))\cdots))</math>. For example, if f is the function <math>x \mapsto x + 1</math>, then the nth repeated application of f is the function <math>x \mapsto x + n</math>. 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 <math>2^n</math>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
Personal tools