CSC 153: Computer Science Fundamentals	Grinnell College	Spring, 2005

Laboratory Exercise Reading

An Introduction to Lists in Scheme

Summary

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.

Introduction

In Scheme, a list is written by enclosing the elements of the list in parentheses. Here are some simple examples:


   (+ x y)
   (this is a list)
   (sqrt x)
   ()

These lists have 3, 4, 2, and 0 components, respectively. The list () with 0 components also is called the empty list or the null list.

Any or all components of a list can, in turn, be lists:

   (* pi (expt r 2))
   (+ (* x x) (* 3 x) 2)
   (all x (if (human x) (mortal x)))
   ( () )
   ((())) 
   ((()())())

In reviewing the second of these examples, (+ (* x x) (* 3 x) 2) is a list with four components:


   +
   (* x x)
   (* 3 x)
   2

List Extraction Functions

Parts of lists can be extracted by car and cdr:

car returns the first element or component of a list.
cdr returns the rest of a list after the first element is removed.

Examples:


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

In each of these examples, note that car and cdr are applied to a list which is introduced with a quote. Since parentheses are used both to group data into a list and to call procedures, the Scheme interactive interface needs to see a single quote at the front of a list literal, so that it will treat it as a datum instead of evaluating it.

Since combinations of car and cdr are frequently used, all combinations up to four uses of car and cdr are defined as functions of the form cxxxr:


   (caar x)    = (car (car x))
   (cadr x)    = (car (cdr x))
   (caddr x)   = (car (cdr (cdr x)))

List Constructor Function:

Two basic functions that construct new list structures are the functions cons and list. If y is a list, then we can think of (cons x y) as adding the new element x to the front of the list y.


   (cons 'a '(b c))    =  (a b c)
   (cons 'a '())       =  (a)
   (cons '(a) '(b))    =  ((a) b)

The list function makes a list out of the elements that follow:


   (list 'a 'b 'c 'd)  = (a b c d)
   (list 'a '(b c))    =  (a (b c))
   (list 'a '())       = (a ())
   (list '(a) '(b))    =  ((a) (b))

List Manipulation Functions

append makes a new list consisting of the members of its argument lists. append takes any number of arguments.


   (append '(a) '(b))       =  (a b)
   (append '(a b) '(c d))   =  (a b c d)
   (append '(a) '(b) '(c))  =  (a b c)

reverse makes a new list that is the reverse of the top level of the list given as its argument.


   (reverse '(a b))         =  (b a)
   (reverse '((a b)(c d)))  =  ((c d)(a b))

length returns the number of components in the [top level] of a list.


   (length '(a))      =  1
   (length '(a b))    =  2
   (length '((a b)))  =  1
   (length '(+ (* x x) (* 3 x) 2)) = 4

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-lists.shtml

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