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 2.22

From Drewiki
Jump to: navigation, search

Contents

Problem, part 1

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

(define (square x) (* x x))
 
(define nil (quote ()))
 
(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

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:

(square-list (list 1 2 3 4))

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:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

This doesn't work either. Explain.

Solution, part 2

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

(square-list (list 1 2 3 4))

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:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (append answer
                      (list (square (car things)))))))
  (iter items nil))

Test:

(square-list (list 1 2 3 4))

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.

Personal tools