An Introduction to Lists in Scheme

Goals

This lab provides practice with lists in Scheme, including the basic operations (cons, car, cdr), list literals, the empty list, and several common built-in procedures.

Steps for this Lab

1. Apply the length function to the following lists that appeared in the reading for this lab.

   
      (+ x y)
      (this is a list)
      (sqrt x)
      ()
      (* pi (expt r 2))
      (+ (* x x) (* 3 x) 2)
      (all x (if (human x) (mortal x)))
      ( () )
      ((())) 
      ((()())())
   

   Check that each list has the number of components you expect.

2. Type the following three expressions into Scheme:

   
      (length 5)
      (length '(+ 2 3))
      (length (+ 2 3))
   

   In each case, explain the result.

3. Review each of the following examples that involve car and cdr.

   
      (car '(a b c))          =  a
      (car '((a) b c))        =  (a)
      (car (car '((a) b c)))  =  a
      (car 'a)     error: a is not a list.
      (car '())    error: () is not a pair.
   
      (cdr '(a b c))          =  (b c)
      (cdr '((a) b c))        =  (b c)
      (cdr (cdr '(a b c)))    =  (c)
      (cdr (car '((a) b c)))  =  ()
      (cdr 'a)     error: a is not a list.
      (cdr '())    error: () is not a pair.
   

   Type some or all of these expressions into Scheme. In each case, be sure you understand the result obtained.

4. Consider the expression (all x (if (human x) (mortal x))). Write Scheme expressions to extract each of the following:

   
      all
      if
      human
   

5. Write a Scheme expression that creates the list (a b c) out of the individual symbols a, b, and c, using the list function.

6. Write a Scheme expression that creates the list (a b c) using only the individual symbols a, b, and c, the nil list, and the cons, car, and cdr functions.

7. Write a Scheme expression that creates the list ((a) (b c)) using only the individual symbols a, b, and c, the nil list, and the cons, car, and cdr functions.

8. Explain what happens when you apply reverse to the lists:

   
      ((a) (b c))
      (+ (* x x) (* 3 x) 2)
   

9. Explain what is returned from each of the following:

   
   (car '(a b c))
   (car (a b c))
   '(car (a b c))
   '(car '(a b c))
   

10. Evaluate the following slightly tricky forms:

    
    (append '(a b c) '( ))
    (list '(a b c) '( ))
    (cons '(a b c) '( ))
    

    In each case, explain why you received the result that you obtain.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-lists.shtml

created January 22, 1997 last revised January 23, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.