SICP Exercise 2.24: Lists, Boxes, Pointers and Trees

Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.6).

Okay, interpreter first:

> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))

Now to produce the corresponding box-and-pointer representation we need to remember that a list is a sequence of pairs where the first element of the n^th pair is the n^th value in the list, and the second element of the n^th pair is either another pair (the (n+1)^th pair) or is nil if the list has n elements. So, for example, at the top level we have a list containing two elements, the first of which is the value 1 and the second is the list produced by (list 2 (list 3 4)). This will be represented by pair with the first element being the value 1 and the second element being another pair. This second pair will have its first element being the list produced by (list 2 (list 3 4)) and its second element being nil.

Applying this reasoning to the whole structure we can produce the following box-and-pointer representation:

When representing lists of lists as trees we can ignore the underlying pair-based representation and simply concentrate on the members of each level of list and their ordering. Now in this case every list has two members: a numeric value as the first member and a sublist as the second member (apart from the last list, where the second member is also a numeric value). This can be represented as a tree as follows:

SICP Exercise 2.23: For Each

The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all -- for-each is used with procedures that perform an action, such as printing. For example,

> (for-each (lambda (x) (newline) (display x))
            (list 57 321 88))
57
321
88

The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.

Well, the definition of map given in the book is:

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

The procedure for-each differs from map in only a couple of points:

• It doesn't need to cons the results of applying proc to (car items) - it just needs to apply the procedure.
• It can just return #t instead of a list.

We could just use map to implement this. After all, map applies proc to each element in turn. It happens to produce a list as a result, but we could throw this away and return #t:

(define (for-each proc items)
  (map proc items)
  #t)

This works as expected:

> (for-each (lambda (x) (newline) (display x))
            (list 57 321 88))
57
321
88 #t

However, this has the drawback that we're generating a potentially very large intermediate list and just throwing it away, so let's try to be a bit more space efficient.

When we try this we'll discover that, while we can replace nil with #t okay, we can't just drop the cons from around the application of proc to the head of the list and the recursion of the tail of the list. While we now want to evaluate a couple of procedures separately in the alternative of if, if doesn't support this. It takes three parameters only: the predicate, consequent and alternative. However, we can get around this by replacing the if with a cond as follows:

(define (for-each proc items)
  (cond ((null? items) #t)
        (else (proc (car items))
              (for-each proc (cdr items)))))

Again, this gives the expected results

> (for-each (lambda (x) (newline) (display x))
            (list 57 321 88))
57
321
88 #t
> (for-each (lambda (x) (newline) (display x))
            (list 1 2 3 4 5))
1
2
3
4
5 #t

SICP Exercise 2.22: Reversed Squares

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.

Back in exercise 2.18 we defined the following procedure for reversing a list:

(define (reverse l)
  (define (iter remaining result)
    (if (null? remaining)
        result
        (iter (cdr remaining) (cons (car remaining) result))))
  (iter l nil))

Now looking carefully at Louis' first iterative implementation of square-list we can see that it is practically identical to our implementation of reverse. Ignoring the different names and formatting, it differs only in the first argument passed to cons when building up the result and equivalent answer lists. In the case of reverse it simply uses (car remaining). However, for Louis' first iterative implementation of square-list it uses (square (car things)). I.e. it squares the car of the remaining elements to process, rather than just using the car of the remaining list directly.

Based on this we can say that what Louis has done is to simply extend the reverse procedure so that it squares each value during the reversal procedure. He's starting with an empty list as the result and then going through the list to square starting with the head, squaring the current value and putting the result onto the head of the result list. So the square of the first element becomes the last item in the list, the square of the second element becomes the second-last item in the list and so on.

Louis' second attempt at producing an iterative implementation of square-list exchanges the two arguments to cons. While this corrects the ordering of the squares it no longer produces a list as the result.

What we find instead is that answer, the result list build up so far, is used as the first argument, while (square (car things)), the square of the current element, is used as the second argument. Now cons only builds a pair - it does not guarantee to produce a validly constructed list. To produce a valid list, although not necessarily a flattened list, from cons the second argument must be itself a valid list. Instead what Louis' procedure does is to return a pair, the second element of which is the square of the last item in the list, while the first element in the pair is itself a pair, with the second element being the square of the second-last item in the list and the first element being a pair... And this nesting of pairs in the first element continues until we reach a pair in which the first element is the empty list and the second element is the square of the first element in the list.

Of course a picture's worth a thousand words, so let's see it in action:

> (square-list (list 1 2 3 4 5 6 7 8 9 10))
((((((((((() . 1) . 4) . 9) . 16) . 25) . 36) . 49) . 64) . 81) . 100)

If you look at this structure closely what you'll see that the pairs that are constructed are a sort of "reverse list structure". A list is constructed of pairs in which the second element of each pair in the list is itself a pair, except for the last pair where it is nil. The values held in the list are the first elements of each pair. What Louis' implementation has constructed is a data structure composed of pairs in which the first element of each pair is itself a pair, except for the first pair where it is nil. In Louis' structure the values are the second elements of each pair.