sicp-ex-2.25



<< Previous exercise (2.24) | Index | Next exercise (2.26) >>


jz

2.25 seems pretty easy, but it gets rather hairy.

a.

  (define items (list 1 3 (list 5 7) 9))
  (car (cdr (car (cdr (cdr items)))))
  ;; => 7

The final car (on the left) is needed to pull the 7 from the (cons 7 nil) list.

To build the cons equivalent of the original:

Step 1: replace (list 5 7) with x:

  (cons 1 (cons 3 (cons x (cons 9 nil))))

Step 2: replace x with cons equivalent:

  (define nil '())
  (cons 1 (cons 3 (cons (cons 5 (cons 7 nil)) (cons 9 nil))))

b.

  (car (car (list (list 7))))
  ;; => 7

c.

  (define a (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
  ;; a =>  (1 (2 (3 (4 (5 (6 7))))))

I thought the answer was just:

  (car (cdr (cdr (cdr (cdr (cdr (cdr a)))))))

but no.

Building up from the inside out:

  (6 7) is (list 6 7)

is by definition

  (cons 6 (cons 7 nil))
  (5 (6 7)) is (list 5 (list 6 7))

Replace (list 6 7) with x for a second to see this is just

  (cons 5 (cons x nil))

Resubstitute the expanded expression for x:

  (cons 5 (cons (cons 6 (cons 7 nil)) nil))
  ----- z -----                       -----

So, any time we add another "wrapping list" we'll need to add the underlined portions, replacing z with the appropriate value.

Therefore,

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

is equivalent to

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

Which is pretty ugly (actually, I'll call this "ugly" in the explanation below).

Anyway, to retrieve the 7, we need to do the following:

  (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr a))))))))))))

Which is also frightful.

Explanation:

The innermost cdr gives the section after the number 1 in ugly, or "(cons (cons 2 ...".

The next car gives "(cons 2 (cons ...").

The next cdr gives "(cons (cons 3 ...".

The next car gives "(cons 3 ...", etc.

Eventually, we get to (cons 7 nil), which is the final car.

Yuck.


 (car (cdr (car (cdr (cdr '(1 3 (5 7) 9)))))) 
 (car (car '((7)))) 
 (car 
  (cdr 
   (car 
    (cdr 
     (car 
      (cdr 
       (car 
        (cdr 
         (car 
          (cdr 
           (car 
            (cdr '(1 (2 (3 (4 (5 (6 7)))))))))))))))))) 

>>> (define third '(1 (2 (3 (4 (5 (6 7))))))) (display (cadr (cadr (cadr (cadr (cadr (cadr third))))))))

to leave a list, you would car. to move up the list, you would cdr. working from the inside, starting from 7. you would need to leave the list (7 is in a list by itself), then move up the list to six with cdr, together they make one cadr. then you are at the same position again with (6 7) instead of the 7. so you would need to leave the (6 7) list then move up a position to 5.

so it is just a repetition of cadr for eace 'wrap'.