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.

## 4 comments:

I had loads of this exercises on my course. Great work ;)

If you know some portuguese » https://dspace.ist.utl.pt/bitstream/2295/133488/1/Problemas%20FP.pdf

here are some exercises I had :D

The Standard Prelude at Programming Praxis has several higher-order functions, including

compose.Hi

So for Exercise 1.43 I had

(define (repeated f n)

(if (= n 1)

f

(repeated (compose f f) (- n 1))))

This procedure worked for some values but didn't for others. Do you know why it is wrong?

Thanks a Lot

mash9p:

(compose f f) applies the function twice, yet you are only subtracting 1 each time.

You could do:

(define (repeated f n)

(if (= n 0)

f

(repeated (compose f f) (- n 2)))))

but this would only work for even cases of n.

Post a Comment