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 explore recursive techniques in which we pass along intermediate computations, often using a recursive helper procedure. When this technique is used in conjunction with a program structure in which the recursive result is returned directly (without accumulated actions to perform), this technique supports tail recursion.
a. Make a copy of helper-recursion-lab.scm
, which contains the definitions from the reading, as well as a few other procedures.
b. Create a list of twelve or so RGB colors and call it
my-colors
. For example,
(define my-color-names (list "palevioletred" "cadetblue" "darkseagreen" "goldenrod" "hotpink" "lightsteelblue" "burlywood" "mistyrose" "salmon" "peru" "plum" "turquoise")) (define my-colors (map color-name->rgb my-color-names))
c. Create a few lists of shades of grey as follows:
(define greys-4 (map (lambda (n) (rgb-new (* 64 n) (* 64 n) (* 64 n))) (list 4 3 2 1))) (define greys-8 (map (lambda (n) (rgb-new (* 32 n) (* 32 n) (* 32 n))) (list 8 7 6 5 4 3 2 1))) (define greys-16 (map (lambda (n) (rgb-new (* 16 n) (* 16 n) (* 16 n))) (list 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)))
a. Test new-sum
, difference
,
new-difference
, and
newer-difference
, to determine whether or not
they behave as they should.
b. Using annotated-difference
, observe the steps
involved in computing the difference of the values in the list
(list 1 2 1 2 1 2 1)
.
a. Rewrite the product
procedure, which computes
the product of a list of values, using the same technique used for
new-sum
.
b. Write a similar my-quotient
procedure.
(Do not call it quotient
,
which is a built-in procedure that is commonly used.)
In the previous
lab, you wrote a procedure, sum-red
, that sums all
the red components in a list of colors. Rewrite that procedure using
the technique of carrying along intermediate values. Your procedure
should look something like the following:
(define sum-red (lambda (colors) (sum-red-helper 0 colors))) (define sum-red-helper (lambda (sum-so-far remaining-colors) ...))
a. Here's a list of colors. Add it to your definitions pane.
(define more-colors (map color-name->rgb (list "red" "green" "blue" "yellow" "black" "white")))
b. Print out the RGB values in both your list of colors and this new list of colors with
>
(map rgb->string my-colors)
>
(map rgb->string more-colors)
c. Here's a procedure using the “results so far” technique that filters out any colors with a red component of at least 128. (You can also find a copy of this procedure in the code accompanying this lab.)
(define rgb-filter-out-high-red (lambda (colors) (rgb-filter-out-high-red-helper null colors))) (define rgb-filter-out-high-red-helper (lambda (colors-so-far remaining-colors) (cond ((null? remaining-colors) colors-so-far) ((<= 128 (rgb-red (car remaining-colors))) (rgb-filter-out-high-red-helper colors-so-far (cdr remaining-colors))) (else (rgb-filter-out-high-red-helper (cons (car remaining-colors) colors-so-far) (cdr remaining-colors))))))
What do you expect this procedure to do when given the empty list?
d. Check your answer experimentally.
e. What do you expect this procedure to do when given the list of the color white?
>
(rgb-filter-out-high-red (list (color->rgb "white")))
f. Check your answer experimentally.
g. What do you expect this procedure to do when given the list of the color black?
>
(rgb-filter-out-high-red (list (color->rgb "black")))
h. Check your answer experimentally.
i. What do you expect this procedure to do when given the list of the color blue?
>
(rgb-filter-out-high-red (list (color->rgb "blue")))
i. Check your answer experimentally.
k. What do you expect this procedure to do when given the list of the colors we created at the begining of this exercise?
>
(rgb-filter-out-high-red more-colors)
l. Check your answer experimentally.
m. What do you expect this procedure to do when given your list of colors as a parameter?
(map rgb->string (rgb-filter-out-high-red my-colors))
n. Check your answer experimentally.
o. In at least one case above, you should have received a somewhat strange result. Do your best to explain that result. If you're not sure, check the notes on this problem. Then, fix the code so that the result is not so strange.
Consider the following procedure.
(define turtle-step! (lambda (turtle) (turtle-forward! turtle 100) (turtle-turn! turtle 180) (turtle-forward! turtle 100) (turtle-turn! turtle 180) (turtle-turn! turtle 7)))
a. Add the following to the beginning of your definitions pane (under the heading “Counting Steps” and then click Run.
(define canvas (image-show (image-new 200 200))) (define counter (turtle-new canvas)) (turtle-teleport! counter 100 100) (define reset! (lambda () (image-select-all! canvas) (image-clear-selection! canvas) (image-select-nothing! canvas) (context-update-displays!) (turtle-teleport! counter 100 100) (turtle-face! counter 0)))
b. What do you expect the following sequence of operations to do?
>
(turtle-step! counter)
>
(turtle-step! counter)
>
(turtle-step! counter)
c. Check your answer experimentally.
d. What do you expect the following sequence of operations to do?
>
(reset!)
>
(turtle-step! counter)
>
(turtle-step! counter)
e. Check your answer experimentally.
f. Now, let's use these ideas to count steps in the various versions
of rgb-brightest
by having the counter draw a
line for each step. We'll start with the first version.
(define rgb-brightest (lambda (colors) (cond ((null? (cdr colors)) (car colors)) ((>= (rgb-brightness (car colors)) (rgb-brightness (rgb-brightest (cdr colors)))) (car colors)) (else (rgb-brightest (cdr colors))))))
Add the line (turtle-step! counter)
immediately
before the cond
statement (that is, as the first
line).
g. How many lines do you expect that the turtle will draw in the following call?
>
(rgb-brightest greys-4)
h. Check your answer experimentally.
i. How many lines do you expect that the turtle will draw in the following call?
>
(rgb-brightest greys-8)
j. Check your answer experimentally.
k. How many lines do you expect that the turtle will draw in the following call?
>
(rgb-brightest greys-16)
l. Check your answer experimentally.
m. How many lines do you expect that the turtle will draw in the following call?
>
(define grays-4 (reverse greys-4))
>
(rgb-brightest grays-4)
n. Check your answer experimentally.
o. How many lines do you expect that the turtle will draw in the following call?
>
(define grays-8 (reverse greys-8))
>
(rgb-brightest grays-8)
p. Check your answer experimentally.
q. Explain why we didn't have you try the same steps again, using a reversed list of sixteen greys.
a. Repeat the previous exercise using the helper version of
rgb-brightest
.
(define rgb-brightest (lambda (colors) (rgb-brightest-helper (car colors) (cdr colors)))) (define rgb-brightest-helper (lambda (brightest-so-far colors-remaining) (if (null? colors-remaining) brightest-so-far (rgb-brightest-helper (if (>= (rgb-brightness brightest-so-far) (rgb-brightness (car colors-remaining))) brightest-so-far (car colors-remaining)) (cdr colors-remaining)))))
b. What do your results suggest to you about this new version of
rgb-brightest
as compared to the prior version?
Although we've primarily used helpers to keep track of one intermediate result, we can certainly pass along more than one intermediate result. For example, in averaging a list of colors, we can keep track of the sum of reds, the sum of greens, the sum of blues, and the count of colors. In the end, we can build a new color from these computed values.
(define rgb-average (lambda (colors) (rgb-average-helper 0 0 0 0 colors))) (define rgb-average-helper (lambda (red-so-far green-so-far blue-so-far count remaining-colors) (if (null? remaining-colors) (rgb-new (/ red-so-far count) (/ green-so-far count) (/ blue-so-far count)) (rgb-average-helper ...))))
a. Fill in the remaining code in the recursive call.
b. Test this code to average white and black.
(rgb->string (rgb-average (list color-white color-black)))
c. Test this code on a few other colors of your choice.
d. What do you expect to have happen if you provide rgb-average
with the empty list?
e. Check your answer experimentally.
The reading provides at least four ways to compute the brightest color in a list. Which do you prefer, and why?
Let's consider the first version of rgb-brightest
.
(define rgb-brightest (lambda (colors) (if (null? (cdr colors)) (car colors) (if (>= (rgb-brightness (car colors)) (rgb-brightness (rgb-brightest (cdr colors)))) (car colors) (rgb-brightest (cdr colors))))))
Suppose we used let
to bind names to the car and the result of the recursive call
(let ((candidate (rgb-brightest (cdr colors))) (alternate (car colors))) ...)
a. Rewrite this version of rgb-brightest
to use
these names in place of the values they name.
b. What effect do you expect this naming to have on the efficiency of the procedure?
c. Check your answer experimentally.
As you may have noticed, the results are presented in
reverse order. That is, the black at the
end of more-colors
is at the front of the list
that results from filtering. Ideally, the values should appear
in the same order in the result.
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.