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)))))))))))))))))) 

timo

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'.

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


Footnote 9. states:

Since nested applications of car and cdr are cumbersome to write, Lisp dialects provide abbreviations for them -- for instance,

(cadr <arg>) = (car (cdr <arg>))

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. The names car and cdr persist because simple combinations like cadr are pronounceable.

But, when I try (cadaddr (list 1 3 (list 5 7) 9)) It returns an error: ;Unbound variable: cadaddr

There is a limit of operations one can concatenate in cxxr format (only four). (Common Lisp HyperSpec: CAR, CDR & etc.)

Since (cdaddr (list 1 3 (list 5 7) 9)) returns (7), we can use (car (cdaddr (list 1 3 (list 5 7) 9))) to solve the first item.

I wrote a procedure to mimic the cxxr function. I don't like this implementation, but that was the way I found to make the function work (I had some problems trying to write a procedure to compare char values, or even evaluating a whole string of a&d's. Using a raw sequence of 0&1's was too cryptic).

 (define a 0) 
 (define d 1) 
 (define (cr items . ad-seq) 
     (define ops (reverse ad-seq)) 
     (define (iter result oper) 
         (if (null? oper)  
             result 
             (cond ((= (car oper) a) (iter (car result) (cdr oper))) 
                   ((= (car oper) d) (iter (cdr result) (cdr oper))) 
                   (else (error "Just cAr or cDr - -  Char Not recognized" (car oper)))))) 
     (iter items ops)) 
          
 ;(1 3 (5 7) 9) 
  
 (cr (list 1 3 (list 5 7) 9) a d a d d) 
 ;Value: 7 
  

ctz

Cool Stuff!

  
 ; create a procedure from a string (using the same format as "cadr", "caaddr", etc) 
 (define (cxxr str)  
   (define (recur str lst) 
     (let ((first (string-ref str 0)) 
           (rest (substring str 1))) 
       (cond ((eq? first #\a) 
              (car (recur rest lst))) 
             ((eq? first #\d) 
              (cdr (recur rest lst))) 
             ((eq? first #\r) 
              lst) 
             (else (error "Unrecognizable symbol:" str))))) 
   (lambda (lst) 
     (if (eq? (string-ref str 0) #\c) 
         (recur (substring str 1) lst) 
         (error "Unrecognizable symbol:" str)))) 
  
 ; find an atom a in the list l and give the string representing the procedure to pick a 
 (define (find a l) 
   (define (searcher l) 
     (cond ((null? l) #f) 
           ((not (pair? l)) 
            (if (eq? a l) 
                "" 
                #f)) 
           (else (let ((a (searcher (car l))) 
                       (d (searcher (cdr l)))) 
                   (cond (a (string-append a "a")) 
                         (d (string-append d "d")) 
                         (else #f)))))) 
   (string-append "c" (searcher l) "r")) 
  
 #| tests: 
 > (find 7 '(1 3 (5 7) 9)) 
 "cadaddr" 
 > ((cxxr "cadaddr") '(1 3 (5 7) 9)) 
 7 
 > (find 7 '(1 (2 (3 (4 (5 (6 7))))))) 
 "cadadadadadadr" 
 > ((cxxr "cadadadadadadr") '(1 (2 (3 (4 (5 (6 7))))))) 
 7 
 |# 

LisScheSic

Review history comments: 1. "(Common Lisp HyperSpec: CAR, CDR & etc.)": https://www.gnu.org/software/mit-scheme/documentation/stable/mit-scheme-ref/Binding-Index.html#Binding-Index_fn_letter-F is better as the reference since the book recommends using MIT Scheme https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/index.html.

MIT Scheme allows substring string [start [end]] https://www.gnu.org/software/mit-scheme/documentation/stable/mit-scheme-ref/Strings.html which is different from R7RS https://standards.scheme.org/corrected-r7rs/r7rs-Z-H-8.html#TAG:__tex2page_index_744.