5.2 Pairs

The simplest structured data construct is a Pair. We draw a Pair as two boxes, each containing a value. We call each box of a Pair a cell. Here is a Pair where the first cell has the value 37 and the second cell has the value 42:

Scheme provides built-in procedures for constructing a Pair, and for extracting each cell from a Pair:conscarcdr

  1. cons: Value $\times $ Value $\rightarrow $ Pair :  
    Evaluates to a Pair whose first cell is the first input and second cell is the second input. The inputs can be of any type.

  2. car: Pair $\rightarrow $ Value :  
    Evaluates to the first cell of the input, which must be a Pair.

  3. cdr: Pair $\rightarrow $ Value :  
    Evaluates to the second cell of input, which must be a Pair.

These rather unfortunate names come from the original LISP implementation on the IBM 704. The name cons is short for “construct”. The name car is short for “Contents of the Address part of the Register” and the name cdr (pronounced “could-er”) is short for “Contents of the Decrement part of the Register”. The designers of the original LISP implementation picked the names because of how pairs could be implemented on the IBM 704 using a single register to store both parts of a pair, but it is a mistake to name things after details of their implementation (see Section 5.6). Unfortunately, the names stuck. We can construct the Pair shown above by evaluating (cons 37 42). DrRacket displays a Pair by printing the value of each cell separated by a dot: (37 . 42). The interactions below show example uses of cons, car, and cdr.

> (define mypair (cons 37 42))  
> (car mypair)  
> (cdr mypair)  

The values in the cells of a Pair can be any type, including other Pairs. For example, this definition defines a Pair where each cell of the Pair is itself a Pair:

(define doublepair (cons (cons 1 2) (cons 3 4)))

We can use the car and cdr procedures to access components of the doublepair structure: (car doublepair) evaluates to the Pair (1 . 2), and (cdr doublepair) evaluates to the Pair (3 . 4).

We can compose multiple car and cdr applications to extract components from nested pairs:

> (cdr (car doublepair))  
> (car (cdr doublepair))  
> ((fcompose cdr cdr) doublepair)``fcompose` from [Section 4.2.1](https://www.otexts.org/node/855)  
> (car (car (car doublepair)))

car: expects argument of type $ < $ pair $ > $; given 1

The last expression produces an error when it is evaluated since car is applied to the scalar value 1. The car and cdr procedures can only be applied to an input that is a Pair. Hence, an error results when we attempt to apply car to a scalar value. This is an important property of data: the type of data (e.g., a Pair) defines how it can be used (e.g., passed as the input to car and cdr). Every procedure expects a certain type of inputs, and typically produces an error when it is applied to values of the wrong type.

We can draw the value of doublepair by nesting Pairs within cells:

Drawing Pairs within Pairs within Pairs can get quite difficult, however. For instance, try drawing (cons 1 (cons 2 (cons 3 (cons 4 5)))) this way.

Instead, we us arrows to point to the contents of cells that are not simple values. This is the structure of doublepair shown using arrows:

Using arrows to point to cell contents allows us to draw arbitrarily complicated data structures such as (cons 1 (cons 2 (cons 3 (cons 4 5)))), keeping the cells reasonable sizes:

Exercise 5.3 Suppose the following definition has been executed:

(define tpair (cons (cons (cons 1 2) (cons 3 4)) 5))

Draw the structure defined by tpair, and give the value of each of the following expressions.

  1. (cdr tpair)
  2. (car (car (car tpair)))
  3. (cdr (cdr (car tpair)))
  4. (car (cdr (cdr tpair)))

Exercise 5.4 Write expressions that extract each of the four elements from fstruct defined by

(define fstruct (cons 1 (cons 2
(cons 3 4))))


Exercise 5.5 Give an expression that produces the structure shown below.