Computer Science Fundamentals (CS153 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
Useful procedures:
cons
,
null?
, and
pair?
Contents
Start DrScheme.
Draw boxandpointer diagrams for each of the following lists:
((x) y z)
(x (y z))
((a) b (c ()))
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))
Draw a boxandpointer representation of the value of the last two expressions in the previous exercise.
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)
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?
.
Recall the sumofnumbertree
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, (numbertree? val)
that
returns true of val is a number tree and false otherwise.
Consider again the sumofnumbertree
procedure.
a. Verify that it works as advertised on the first example.
(sumofnumbertree (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 sumofnumbertree
to return when
given (cons 10 11)
as a parameter? Verify your answer
experimentally.
e. What do you expect sumofnumbertree
to return when
given the empty list as a parameter? Verify your answer experimentally.
f. What do you expect sumofnumbertree
to return when
given (list 1 2 3 4 5)
as a parameter? Verify your answer
experimentally.
Define and test a procedure named conscellcount
that takes
any Scheme value and determines how many boxes would appear in its
boxandpointer 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 conscellcount
also tallies the number
of times cons
was invoked during the construction of its
argument.)
For example, the structure in the following boxandpointer diagram
contains seven conscells, so when you apply conscellcount
to that structure, it should return 7. On the other hand, the string
"sample"
contains no conscells, so the value of
(conscellcount "sample")
is 0.
Use conscellcount
to find out how many cons cells are needed
to construct the list
(0 (1 (2 (3 (4)))))
Draw a boxandpointer diagram of this list to check the answer.
If you were able to complete the primary exercises with time to spare, you might want to consider the following problems:
listp?
without using if
or
cond
.
numsyms
, that counts the number
of symbols in a symbol tree.
In case you don't want to switch documents, here is the code for
sumofnumbertree
.
;;; Procedure: ;;; sumofnumbertree ;;; 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 sumofnumbertree (lambda (ntree) (if (pair? ntree) (+ (sumofnumbertree (car ntree)) (sumofnumbertree (cdr ntree))) ntree)))
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)))))
Monday, 18 September 2000 [Samuel A. Rebelsky]
http://www.math.grin.edu/~stone/courses/scheme/pairs.xhtml
(by Henry Walker and John Stone).
That URL no longer seems to exist. I believe that it is
archived at
http://www.cs.grinnell.edu/~stone/courses/scheme/spring2000/pairs.xhtml
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/pairs.html
.
Wednesday, 21 February 2001 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/pairs.html
.
Sunday, 29 September 2002 [Samuel A. Rebelsky]
listp?
and
numbertree?
).
If You Have Extra Timesection.
Monday, 30 September 2002 [Samuel A. Rebelsky]
sumofnumbertree
problem (currently problem 7).
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/pairs.html
.
Wednesday, 12 February 2003 [Samuel A. Rebelsky]
sumofnumbertree
(whoops!).
http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/pairs.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
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
.
; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu