SICP 1.41 - 1.43: Procedures as Returned Values

From SICP section 1.3.4 Procedures as Returned Values

Exercise 1.41 asks us to define a procedure double that takes a procedure of one argument as its argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should return a procedure that adds 2. We need to be able to use our double procedure to evaluate expressions like

(((double (double double)) inc) 5)

Just like the previous exercise, we can use lambda to return a procedure from a procedure.

(define (double f)
  (lambda (x) (f (f x))))

We'll also need to define a couple of procedures to test with.

(define (inc x) (+ x 1))
(define (square x) (* x x))

> ((double inc) 1)
3
> ((double square) 2)
16

As you can see, the name double is a little bit misleading. The procedure doesn't apply the input procedure then double the result, it applies the input procedure the applies it again to the result.
So in the first test the input parameter 1 is incremented, then the resulting value is incremented again. Likewise in the second test, the input parameter 2 is squared, then the result is squared.

Here's the result from running the test case given in the text:

> (((double (double double)) inc) 5)
21

Here we have nested calls to double itself. One set of nested calls to double has the effect of quadrupling the input procedure. Nesting it again results in 16 calls to inc.



Exercise 1.42 asks us to define a procedure compose that implements the composition of two functions that are supplied as input parameters. This is very similar to the double procedure we saw in the last exercise, but instead of applying the same procedure twice, we're given two different procedures.

If we evaluate

((compose square inc) 6)

we should get back a value of 49 because the input 6 will first be incremented then squared.

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

We can run two tests to show the order that the input procedures are evaluated.

> ((compose square inc) 6)
49
> ((compose inc square) 6)
37

Exercise 1.43 asks us to write a procedure that takes a procedure and a number n as arguments, and returns a procedure that applies the input procedure n times. We can make use of the compose procedure from the previous exercise.

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

Repeatedly incrementing a value n times should give us the expected result of just adding n to the original value.

> ((repeated inc 2) 5)
7
> ((repeated inc 10) 10)
20

Squaring a value twice has the effect of raising it to the 4^th power.

> ((repeated square 2) 5)
625

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.