# Laboratory: Pairs and Pair Structures

Useful procedures: `cons`, `null?`, and `pair?`

Contents

## Exercises

Start DrScheme.

### Exercise 1: Some Pictures

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

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

### Exercise 2: Some Pairs

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 null)`
• `(cons 'a "null")`
• `(cons 'a "()")`
• `(cons null 'a)`
• `(cons null (cons null null))`

### Exercise 3: More Pictures

Draw a box-and-pointer representation of the value of the last two expressions in the previous exercise.

### Exercise 4: Are They Pairs?

What do you think that `pair?` will return for each of the following? How about `list?`. Confirm you answer experimentally and explain any that you found particularly tricky.

• `(cons 'a 'b)`
• `(cons 'a (cons 'b 'c))`
• `(cons 'a null)`
• `null`
• `(list 'a 'b 'c)`
• `(list 'a)`
• `(list)`

### Exercise 5: Is It A List?

You may recall that I told you that many kinds of data are defined recursively. For example, a list is either (1) null or (2) cons of anything and a list.

Using that recursive definition of lists, write a procedure, `(listp? val)`, that determines whether or not val is a list.

You may not use `list?` in your definition of `listp?`.

### Exercise 6: Number Trees

Recall the `sum-of-number-tree` procedure from the reading on pairs. That procedure only worked on number trees, trees built from cons cells and numbers.

A number tree is another recursively defined data structure. A number tree is either (1) a number or (2) cons of a number tree and a number tree.

Using that recursive definition of number trees, write a procedure, `(number-tree? val)` that returns true of val is a number tree and false otherwise.

### Exercise 7: Summing Number Trees

Consider again the `sum-of-number-tree` procedure.

a. Verify that it works as advertised on the first example.

```(sum-of-number-tree (cons (cons (cons 0 1)
(cons 2 3))
(cons (cons 4 5)
(cons 6 7))))
```

b. Verify that it works as advertised on a single number.

c. Verify that it works as advertised on a pair of numbers.

d. What do you expect `sum-of-number-tree` to return when given `(cons 10 11)` as a parameter? Verify your answer experimentally.

e. What do you expect `sum-of-number-tree` to return when given the empty list as a parameter? Verify your answer experimentally.

f. What do you expect `sum-of-number-tree` to return when given `(list 1 2 3 4 5)` as a parameter? Verify your answer experimentally.

### Exercise 8: Counting Cons Cells

Define and test a procedure named `cons-cell-count` that takes any Scheme value and determines how many boxes would appear in its box-and-pointer diagram. (The data structure that is represented by such a box, or the region of a computer's memory in which such a structure is stored is called a cons cell. Every time the `cons` procedure is used, explicitly or implicitly, in the construction of a Scheme value, a new cons cell is allocated, to store information about the car and the cdr. Thus `cons-cell-count` also tallies the number of times `cons` was invoked during the construction of its argument.)

For example, the structure in the following box-and-pointer diagram contains seven cons-cells, so when you apply `cons-cell-count` to that structure, it should return 7. On the other hand, the string `"sample"` contains no cons-cells, so the value of `(cons-cell-count "sample")` is 0. Use `cons-cell-count` to find out how many cons cells are needed to construct the list

```(0 (1 (2 (3 (4)))))
```

Draw a box-and-pointer diagram of this list to check the answer.

## If You Have Extra Time

If you were able to complete the primary exercises with time to spare, you might want to consider the following problems:

• Write `listp?` without using `if` or `cond`.
• Write a procedure, `num-syms`, that counts the number of symbols in a symbol tree.

## Notes

### Notes on Exercise 7

In case you don't want to switch documents, here is the code for `sum-of-number-tree`.

```;;; Procedure:
;;;   sum-of-number-tree
;;; Parameters:
;;;   ntree, a number tree
;;; Purpose:
;;;   Sums all the numbers in ntree.
;;; Produces:
;;;   sum, a number
;;; Preconditions:
;;;   ntree is a number tree.  That is, it consists only of numbers
;;;   and cons cells.
;;; Postconditions:
;;;   sum is the sum of all numbers in ntree.
(define sum-of-number-tree
(lambda (ntree)
(if (pair? ntree)
(+ (sum-of-number-tree (car ntree))
(sum-of-number-tree (cdr ntree)))
ntree)))
```

### Notes on Exercise 8

If, for some reason, you are having trouble creating the list

`(0 (1 (2 (3 (4)))))`

try

```(list 0 (list 1 (list 2 (list 3 (list 4)))))
```

## History

Monday, 18 September 2000 [Samuel A. Rebelsky]

Wednesday, 21 February 2001 [Samuel A. Rebelsky]

Sunday, 29 September 2002 [Samuel A. Rebelsky]

• Updated exercises 2 and 3 slightly.
• Updated formatting slightly.
• Added new exercises 5 and 6 (`listp?` and `number-tree?`).
• Added the If You Have Extra Time section.

Monday, 30 September 2002 [Samuel A. Rebelsky]

Wednesday, 12 February 2003 [Samuel A. Rebelsky]

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 6 09:19:56 2003.
The source to the document was last modified on Wed Feb 12 08:54:30 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/pairs.html`.

Samuel A. Rebelsky, rebelsky@grinnell.edu