SICP Exercise 2.22

Question

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

(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?

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.

Answer

Actually, these two algorithms produce two slightly different outputs. While the first one just returns the list in reverse order as described, the second one returns a nested list (but in the right order). Let’s look at the two results next to each other:

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

Let’s start with the first algorithm. In order to understand why it behaves the way it does, it may help to evaluate the execution of iter using the substitution model (not strictly in order so as to make it more readable). So this is what it would look like:

(iter (list 1 2 3) nil)

(iter (cdr (list 1 2 3))
      (cons (square (car (list 1 2 3)))
            nil))

(iter (list 2 3)
      (cons (square 1) nil))

(iter (list 2 3) (cons 1 nil))

(iter (list 2 3) (list 1))

(iter (cdr (list 2 3))
      (cons (square (car (list 2 3)))
            (list 1)))

(iter (list 3)
      (cons (square 2) (list 1)))

(iter (list 3) (cons 4 (list 1)))

(iter (list 3) (list 4 1))

(iter (cdr (list 3))
      (cons (square (car (list 3)))
            (list 4 1)))

(iter nil
      (cons (square 3)
            (list 4 1)))

(iter nil (cons 9 (list 4 1)))

; return answer since things is nil
(iter nil (list 9 4 1))

(list 9 4 1)

As expected, we receive the array in inverted order in return. Looking at the way the procedure evaluates, it makes sense: the array is evaluated beginning to end, but cons is called with the current result first and then the previous results. It also makes sense then to assume that flipping the order within the cons would fix this problem. But, as we saw, this still gives a wrong result, namely a nested list.

So let us do for this second implementation what we just did for the first and evaluate iter step by step.

(iter (list 1 2 3) nil)

(iter (cdr (list 1 2 3))
      (cons nil
            (square (car (list 1 2 3)))))

(iter (list 2 3)
      (cons nil (square 1)))

(iter (list 2 3) (list (nil 1)))

At this point, we can already see where the problem is. nil at the end of a list simply marks the end, but at the beginning of a list, it is interpreted as an empty list. You can verify this for yourself:

(list nil 1)

Result:

(() 1)