MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999

Recitation -- Friday, February 12

1. Cons Pairs and Lists

Recall the contract for cons, car, cdr, pair?, and null?.

There are three main methods of representing cons and list structures. You should be able to convert between them.

2. Other Accessors

In scheme, we often want to access elements deep in a cons structure. Therefore, the following accessors have been defined to help us out:

For lists, we also often want to easily access the n'th element of a list. The accessors first, second, third, ..., tenth are defined to access the corresponding values of a list. For example,

 
(sixth (list 1 2 3 4 5 6 7 8 9)) 
;Value: 6

How could you define first, second, third, and fourth using the c???r functions?

3. Practice

Draw box and pointer diagrams and write what will Scheme print for the following expressions.

 
 (define x (cons 5 2))
 (car x)
 ;Value: 5 
 (cdr x)
 ;Value: 2 
 (car (cdr x))
 ;Error: 2 passed car 
 (define y (cons sqrt x))
 (car (cdr y))
 ;Value: 5 
 (car y)
 ;Value: #[compiled-procedure 24] 
 (define z (cons ((car y) 49) x))
 z
 ;Value: (7 5 . 2) 

Write a Scheme expression that will print each of the following. Also draw box and pointer diagrams.

 
  (list 1 2 3) 
;Value: (1 2 3)
  (cons 1 (cons 2 3)) 
;Value: (1 2 . 3)
  (cons (list 1 (list 2)) 3) 
;Value: ((1 (2)) . 3)

Write Scheme expressions that correspond to the following.

4. Functions on Lists

We saw that we have the primitive function pair? to see if an object is a pair. What if we wanted to write the function list? to see if an object is a list?

What is the contract for list? (list? (list )) == #t

What's another way to write it?

 
(list? nil) == #t
(list? (cons x l)) == #t   ==>   (list? l)

Now, how can we write list? in scheme?

 
(define (list? x)
 
  (or (null? x)
      (and (pair? x)
           (list? (cdr x))))
 )

What is the Order of Growth of pair? and list? ?

pair? is and list? is , where n is the length of the list.

• About this document ...