Computer Science Fundamentals (CS153 2004S)

Laboratory: Pairs and Pair Structures

Summary: In this laboratory, you will further ground your understanding of what happens behind the scenes when Scheme deals with lists and other pair-based structures.

Useful procedures: cons, null?, and pair?


Related Pages:


Exercise 0: Preparation

Start DrScheme.

Exercise 1: Some Pictures

Draw box-and-pointer diagrams for each of the following lists. I'll wander around and check your work. You may also want to compare your answer with your neighbor's.

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.

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.

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.

a diagram including seven divided rectangles which represent cons cells

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:


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)))

Notes on Exercise 8

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

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


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



Monday, 18 September 2000 [Samuel A. Rebelsky]

Wednesday, 21 February 2001 [Samuel A. Rebelsky]

Sunday, 29 September 2002 [Samuel A. Rebelsky]

Monday, 30 September 2002 [Samuel A. Rebelsky]

Wednesday, 12 February 2003 [Samuel A. Rebelsky]

Tuesday, 10 February 2004 [Sammuel 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 Fri May 7 09:44:19 2004.
The source to the document was last modified on Tue Feb 10 22:59:14 2004.
This document may be found at

Valid HTML 4.0 ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,