Pairs

Box-and-pointer diagrams

As we have seen, Scheme uses cons to build lists. We now consider a graphical way to represent the result of a cons procedure. The basic idea is to use a rectangle, divided in half, to represent the result of the cons. From the first half of the rectangle, we draw an arrow to the first element of a list, its car; from the second half of the rectangle, we draw an arrow to the rest of the list, its cdr. When the cdr is empty, we draw a diagonal line through the right half of the rectangle to indicate that the list stops at that point.

For instance, the value of the expression (cons 'a '()) would be represented in this notation as follows:

a divided rectangle with A on the left and the null list on the right

Since the value of the expression (cons 'a '()) is the list (a), this diagram represents (a) as well.

Now consider the value of the expression (cons 'b '(a)) -- in other words, the list (b a). Here, we draw another rectangle, where the head points to b and the tail points to the representation of (a) that we already have seen. The result is:

a divided rectangle with B on the left and a pointer to the preceding diagram on the right

Similarly, the list (d c b a) is the value of the expression (cons 'd (cons 'c (cons 'b (cons 'a '())))) and would be drawn as follows:

a diagram including four divided rectangles

A similar approach may be used for lists that have other lists as elements. For example, consider the list ((a) b (c d) e). This is a list with four components, so at the top level we will need four rectangles, just as in the previous example for the list (d c b a). Here, however, the first component designates the list (a), which itself involves the box-and-pointer diagram already discussed. Similarly, the list (c d) has two boxes for its two components (as in the diagram for (b a) above). The resulting diagram is:

a diagram including seven divided rectangles

Additional discussion and examples may be found in the first few pages of section 11.3 of the textbook.

Throughout these diagrams, the null list is represented by a null pointer, a diagonal line. Thus, the list containing the null list, (()) -- that is, (cons '() '()) -- is represented by a rectangle with lines through both halves:

a divided rectangle with a null list in each half

Exercise 1

Draw box-and-pointer diagrams for each of the following lists:

((x) y z)
(x (y z))
((a) b (c ()))

Pairs that are not lists

While we consistently have discussed cons in the context of lists, Scheme allows cons to be applied even when the second argument is not a list. For example, (cons 'a 'b) is a legal expression; its value is represented by the following box-and-pointer diagram:

a divided rectangle with A on the left and B on the right

When Scheme is asked to print out such a value, it uses dot notation: (a . b) Here, the dot indicates that cons has been applied, but the second argument is not a list. Similarly,
(cons 1 'a) may be written (1 . a) and (cons "Henry" "Walker") produces ("Henry" . "Walker"). Using a box-and-pointer representation, this last result would be drawn as follows:

a divided rectangle with the string Henry on the left and the string Walker on the right

The car and cdr procedures can be used to recover the halves of one of these dotted pair structures:

> (car '(a . b))
a
> (cdr '(a . b))
b

Note that the cdr of such a structure is not a list.

Exercise 2

Enter each of the following expressions into Scheme. In each case, explain why Scheme does or does not use the dot notation when displaying the value.

(cons 'a "Walker")
(cons 'a '())
(cons '() 'a)
(cons '() '())

Exercise 3

Draw a box-and-pointer representation of the value of each expression in the previous exercise.

The pair? predicate returns #t when it is given any dotted-pair structure, or indeed any structure that cons can possibly return as its value. (Basically, pair? determines whether the object it is given is one of those two-box rectangles.)

Association lists

Consider the organization in a simple telephone directory: a sequence of entries, each including a name and a telephone number.

One way to write such a directory in Scheme is to consider each entry as a pair, such as ("Walker" . 4208) or ("Stone" . 3181). An entire directory, then, would be a list of such entries:

(define math-cs-directory
  '(("Adelberg" . 4201) ("Chamberland" . 4207) ("Herman" . 4202) ("Imig" . 4205)
    ("Jepsen" . 4203) ("Jones" . 4204) ("Rebelsky" . 4410) ("Shierholz" . 4206) 
    ("Stone" . 3181) ("Walker" . 4208) ("Wolf" . 4209)))

In Scheme, such a list of pairs is called an association list or alist.

As the telephone-directory example illustrates, a particularly common application of association lists involves looking for a desired name or first component of a pair and retrieving the second component of a pair. Thus, the first component of each pair (the car of a pair) often is called a key, and the cdr of the pair is its associated data or value. For example, in the above illustration, "Herman", "Stone", and "Walker" are keys, and the telephone numbers are the associated data. Thus an association list is a simple way to implement a small database.

Since such applications are very common, Scheme provides procedures to retrieve from an association list the pair containing a specified key. The most frequently used procedure of this kind is assoc. Given a key and association list, assoc returns the first pair with the given key. If the key does not occur in the association list, then assoc returns #f. For example, (assoc "Stone" math-cs-directory) returns ("Stone" . 3181), while (assoc "Smith" math-cs-directory) returns #f.

To find the telephone number corresponding to a given name, we could apply the cdr procedure to the result of assoc:

(define look-up-telephone-number
  (lambda (name)
    (if (assoc name math-cs-directory)
        (cdr (assoc name math-cs-directory))
        'unlisted)))

Now (look-up-telephone-number "Stone") returns 3181 and (look-up-telephone-number "Smith") returns the symbol unlisted.

Exercise 4

Define an association list birthdays which associates peoples' surnames (as strings) with their birthdays (again, as strings). Thus, a typical entry might be ("Lincoln" . "February 12, 1809").

Exercise 5

Use the assoc procedure to search the birthdays association list for someone who is on the list and for someone who is not on the list.

Exercise 6

Redefine birthdays so that it includes entries for two people who have the same surname -- say, John Adams (born October 30, 1735) and John Quincy Adams (born July 11, 1767). What happens if you try to retrieve a pair with assoc using this common key?

Exercise 7

What happens if you search by date instead of by person? (For example, you might try (assoc "February 12, 1809" birthdays).) Define a Scheme procedure reverse-lookup that takes two arguments, an association list alist and an associated datum val, and returns a pair from alist that has val as its second component.

The assoc procedure is actually one of three related built-in procedures in Scheme; the other two are assq and assv. Each of these procedures scan association lists for keys. They differ only in the test used for determining when a key is found:

assoc uses the predicate equal? for comparing the key sought with the key components of the entries in the association list.
assq uses the predicate eq? for those comparisons.
assv uses the predicate eqv? for those comparisons.

(See the earlier lab ``Lists, Booleans, and predicates'' to refresh your memory about the details of these predicates.)

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1998/pairs.html

created February 21, 1997
last revised June 21, 1998

Henry Walker (walker@math.grin.edu) and John David Stone (stone@math.grin.edu)