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
Scheme provides built-in procedures for constructing a Pair, and for extracting each cell from a Pair:conscarcdr
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.
car: Pair $\rightarrow $ Value :
Evaluates to the first cell of the input, which must be a Pair.
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”.
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
(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
> (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:
We can use the
cdr procedures to access components of the
(car doublepair) evaluates to the Pair
(cdr doublepair) evaluates to the Pair
(3 . 4).
We can compose multiple
cdr applications to extract
components from nested pairs:
> (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
is applied to the scalar value
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
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:
Draw the structure defined by
tpair, and give the value of each of the following
(car (car (car tpair)))
(cdr (cdr (car tpair)))
(car (cdr (cdr tpair)))
Exercise 5.4 Write expressions that extract each of the four
fstruct defined by
(cons 3 4))))
Exercise 5.5 Give an expression that produces the structure shown below.