SICP - Solution: Exercise 1.43

October 29, 2018

Exercise 1.43 #

If $f$ is a numerical function and $n$ is a positive integer, then we can form the $n^{\text{th}}$ repeated application of $f$, which is defined to be the function whose value at $x$ is ${f(f(\dots(f(x))\dots))}$. For example, if $f$ is the function ${x\mapsto x+1}$, then the $n^{\text{th}}$ repeated application of f is the function ${x\mapsto x+n}$. If f is the operation of squaring a number, then the $n^{\text{th}}$ repeated application of $f$ is the function that raises its argument to the ${2^n\text{-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 $n^{\text{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.

Solution #

The solution took me some time to figure out. Manipulating higher-order functions like this can be tough, especially without a clear type signatures for each function. DrRacket trace function was most useful.

(define (square x) (* x x))

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

(display ((repeated square 2) 5)) (newline)

Note: (- 1 n) is not the same as (- n 1) #

Small gotcha that I found while working on this exercise:

(define x 10)
(display (- 1 x)) (newline)
(display (- x 1)) (newline)

Evaluates to:

-9
9