Laboratory: Pairs and Pair Structures

Useful procedures: cons, null?, and pair?

Contents

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Some Pictures
  • Exercise 2: Some Pairs
  • Exercise 3: More Pictures
  • Exercise 4: Are They Pairs?
  • Exercise 5: Is It A List?
  • Exercise 6: Number Trees
  • Exercise 7: Summing Number Trees
  • Exercise 8: Counting Cons Cells
• If You Have Extra Time
• Notes
  • Notes on Exercise 7
  • Notes on Exercise 8

Exercises

Exercise 0: Preparation

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