SICP Exercise 2.25: Nested cars and cdrs

Give combinations of cars and cdrs that will pick 7 from each of the following lists:

(1 3 (5 7) 9)

((7))

(1 (2 (3 (4 (5 (6 7))))))

We can take this exercise quite literally and just use car and cdr. Let's do that to start with. Then we'll look at using abbreviations for the nested combinations as outlined in footnote 9 in this section.

Let's start at the top then. (list 1 3 (list 5 7) 9) defines a list with 4 elements, the third of which is a list of two elements, the last element of which is 7. First of all we need to get to the third element in the outer list. We know that, when processing lists, car gives us head of the current list and cdr gives us the tail of the current list. Taking the tail of the outer list will give us the three tail elements, of which the second is the one we want, so we need to take the tail of this again to give us the tail two elements, and then take the head to give us the inner list. The inner list has 7 as its second element, so we need to take the tail of this list, which is a single element list (i.e. a pair with a value, 7 in this case, as the first element and nil as the second). So we finally take the head of this list to get to 7.

In practice this is:

> (car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
7

The second list, (list (list 7)), is a list with a single element which is itself a list with a single element, 7. So to get to 7 we can take the head of the outer list, giving us the inner list, and then take the head of the inner list, to give us 7. In other words:

> (car (car (list (list 7))))
7

In the case of the third list we have a repeated structure running through it. Starting at the outer list we have a list of two elements: the first is a numeric value and the second is itself a list of the same structure. This nesting of lists through the second element repeats all the way down to the sixth list, where the second element is the value 7 instead of another list. Now to get the second value of a list we need to take the head of the tail of the list (i.e. (car (cdr list))). As the value 7 is the second element of the sixth list in this repeated structure, we can simply repeat this action six times to pick it out:

> (car
    (cdr
      (car
        (cdr
          (car
            (cdr
              (car
                (cdr
                  (car
                    (cdr
                      (car
                        (cdr
                          (list 1
                                (list 2
                                      (list 3
                                            (list 4
                                                  (list 5
                                                        (list 6
                                                              7))))))))))))))))))
7

All these nested cars and cdrs are pretty ugly though and, as noted in the footnote referenced above, Scheme provides abbreviations for such nesting. The footnote states that "The names of all such procedures start with c and end with r. Each a between them stands for a car operation and each d for a cdr operation, to be applied in the same order in which they appear in the name." However, we can't just change e.g. the last one to (cadadadadadadr <list>). The Scheme standard only requires that interpreters support combinations up to 4 deep. We can still nest those though, and so reduce the levels of nesting greatly:

> (car (cdaddr (list 1 3 (list 5 7) 9)))
7
> (caar (list (list 7)))
7
> (cadadr (cadadr (cadadr (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))))
7

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