SICP exercise 2.22

From Drewiki

Problem, part 1

Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:

Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

Solution, part 1

Let's verify the first claim:

Output:

(16 9 4 1)

The answer is reversed because the argument list is traversed in order, from first to last, but squares are added successively to the front of the answer list via cons. We want to add squares to the end of the answer list, in first-in/first-out (FIFO) fashion.

Problem, part 2

Louis then tries to fix his bug by interchanging the arguments to cons:

This doesn't work either. Explain.

Solution, part 2

Let's look at the result of this square-list implementation:

Output:

((((() . 1) . 4) . 9) . 16)

We haven't encountered this strange representation in the text yet, but it's certainly not what Louis desired. The problem with this implementation is that the arguments to cons are flipped: the first argument to cons is answer, which is a list, and the second argument is an integer. To build a list of integers requires a sequence of pairs created by nested conses, where the first argument is an integer and the second is a list created by cons (or the empty list).

One possible solution to the problem of implementing an iterative version of square-list is to use append:

Test:

Output:

(1 4 9 16)

Note that this implementation is similar to the implementation of reverse that we devised in our answer to exercise 2.18.