CSC151.01 2009F Functional Problem Solving : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Summary: In this laboratory, you will further explore issues of recursion over trees introduced in the reading on pairs and pair structures and continued in the reading on trees.
a. Make sure that you have the reading on pairs and pair structures and the reading on trees open in separate tabs and windows.
b. Make sure that you have a piece of paper and writing instrument handy.
As you may recall from the reading, we have defined color trees as follows.
t1
and t2
are
color trees, then so is (cons
t1
t2
)
.
Using this recursive definition, write a procedure,
(color-tree? val)
that returns true
(#t
) if val is a color tree and false
(#f
) otherwise.
Recall the render-color-tree!
procedure from the
reading.
;;; Procedure: ;;; render-color-tree! ;;; Parameters: ;;; ctree, a tree of colors ;;; image, an image ;;; left, an integer ;;; top, an integer ;;; width, an integer ;;; height, an integer ;;; Purpose: ;;; Render the tree into the portion of the image bounded at ;;; the left by left, at the top by top, and with the specified ;;; width and height. ;;; Produces: ;;; [Nothing; Called for the side effect.] ;;; Preconditions: ;;; [The usual] ;;; Postconditions: ;;; The tree has now been rendered. (define render-color-tree! (lambda (ctree image left top width height) (cond ((pair? ctree) (render-color-tree! (car ctree) image left top (/ width 2) height) (render-color-tree! (cdr ctree) image (+ left (/ width 2)) top (/ width 2) height)) (else (image-select-rectangle! image REPLACE left top width height) (context-set-fgcolor! ctree) (image-fill-selection! image) (context-update-displays!) (image-select-nothing! image)))))
a. Add render-color-tree!
to your definitions window.
b. Create a new 200x200 image named canvas
.
c. What effect do you expect the following instruction to have?
>
(render-color-tree! "blue" canvas 0 0 200 200)
d. Check your answer experimentally.
e. What effect do you expect the following instruction to have?
>
(render-color-tree! (cons "black" "red") canvas 0 0 200 200)
f. Check your answer experimentally.
g. What effect do you expect the following instruction to have?
>
(render-color-tree! (cons (cons "green" "yellow") "orange") canvas 0 0 200 200)
h. Check your answer experimentally.
i. What effect do you expect the following instruction to have?
>
(render-color-tree! (cons "red" (cons (cons "blue" "purple") "black")) canvas 0 0 200 200)
j. Check your answer experimentally.
k. Create a color tree that you might be able to render in some interesting fashion.
Rewrite render-color-tree!
so that it splits the
image vertically rather than horizontally.
a. What preconditions should render-color-tree!
have?
b. Use the color-tree?
predicate from an earlier
exercise to rewrite render-color-tree!
so that
it reports an appropriate error if its preconditions are not met.
Use husk-and-kernel style, checking the preconditions in the husk.
c. Some programmers consider it inappropriate to scan a tree twice,
once to make sure that it's valid and once to use the tree.
Rewrite render-color-tree!
so that it checks
for and reports errors only when it is at one of the non-pair values.
Let's explore trees more generally. As you've noted, trees are built from cons cells (pairs). Sometimes it is useful to find out how many cons cells are in a tree.
a. 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.
In answering this question, you should consider whether each value, in
turn, is a pair using the pair?
predicate.
b. Use cons-cell-count
to find out how many cons
cells are needed to construct the list
(0 (1 (2 (3 (4)))))
See the notes at the end of the lab if you have trouble creating that list.
c. Draw a box-and-pointer diagram of this list to check the answer.
One potentially interesting way to experiment with color trees is to have a procedure build those trees. How? We might provide the procedure with an intended size of the tree.
a. Using this technique, write a procedure, (
, that randomly builds a black and white tree of the appropriate size.
random-bw-tree
size
)
b. Using this technique, write a procedure, (
, that builds a random color tree of the desired size, randomly selecting the color from the list random-color-tree
size
colors
)colors
.
Create a new version of render-color-tree!
that
has an extra parameter, vsplit?
, a Boolean value. If the
Boolean is true, when render-color-tree!
should
split the area vertically (as it currently does). If the Boolean is
false, render-color-tree!
should split the area
horizontally. In both cases, the recursive calls should negate that
Boolean value so that the splits alternate between vertical and
horizontal.
If you find that you have extra time, you might want to attempt one or more of the following problems.
As you may recall, a tree is either (a) a non-pair value or (b) the cons of two trees. In the reading, you saw a procedure that counted the number of values in a tree. In this lab, you wrote a procedure that counted the number of cons cells (pairs) in a tree. What is the relationship between the numbers returned by those two procedures?
a. Write a procedure, (
,
that determines whether color-tree-contains?
ctree
color
)color
appears anywhere in
ctree
. (We may have written a similar procedure
during the class discussion. If so, you can start with that procedure.)
b. Rewrite the procedure to determine if a color nearby to color
appears somewhere in ctree
. (You might say that two colors
are nearby if their red, green, and blue components all differ by less
than sixteen.)
c. Write (
, a generalized version of
tree-contains
tree
value
)color-tree-contains
that works with a
heterogeneous tree (that is, a tree that contains multiple kinds of values).
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.