Fundamentals of Computer Science I: Media Computing (CS151.02 2007F)
[Skip to Body]
Primary:
[Front Door]
[Glance]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[Assignments]
[EBoards]
[Examples]
[Exams]
[Handouts]
[Labs]
[Outlines]
[Projects]
[Readings]
[Reference]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151.01 2007F (Davis)]
[CSC151 2007S (Rebelsky)]
[CSCS151 2005S (Stone)]
This lab is also available in PDF.
Summary: In this laboratory, you will explore some basic concepts in recursing over lists.
Contents:
Reference:
Here are the definitions from the reading.
;;; Procedure: ;;; sum ;;; Parameters: ;;; numbers, a list of numbers. ;;; Purpose: ;;; Find the sum of the elements of a given list of numbers ;;; Produces: ;;; total, a number. ;;; Preconditions: ;;; All the elements of numbers must be numbers. ;;; Postcondition: ;;; total is the result of adding together all of the elements of numbers. ;;; If all the values in numbers are exact, total is exact. ;;; If any values in numbers are inexact, total is inexact. (define sum (lambda (numbers) (if (null? numbers) 0 (+ (car numbers) (sum (cdr numbers)))))) (define rgb.filteroutdark (lambda (colors) (cond ((null? colors) null) ((rgb.dark? (car colors)) (rgb.filteroutdark (cdr colors))) (else (cons (car colors) (rgb.filteroutdark (cdr colors)))))))
The latter procedure requires rgb.dark?
, which follows.
;;; Procedure: ;;; rgb.dark? ;;; Parameters: ;;; color, an RGB color ;;; Purpose: ;;; Determine if the color appears dark. ;;; Produces: ;;; dark?, a Boolean (define rgb.dark? (lambda (color) (> 33 (rgb.brightness color)))) ;;; Procedure: ;;; rgb.brightness ;;; Parameters: ;;; color, an RGB color ;;; Purpose: ;;; Computes the brightness of color on a 0 (dark) to 100 (light) scale. ;;; Produces: ;;; b, an integer ;;; Preconditions: ;;; color is a valid RGB color. That is, each component is between ;;; 0 and 255, inclusive. ;;; Postconditions: ;;; If color1 is likely to be perceived as lighter than color2, ;;; then (brightness color1) > (brightness color2). (define rgb.brightness (lambda (color) (round (* 100 (/ (+ (* .30 (rgb.red color)) (* .59 (rgb.green color)) (* .11 (rgb.blue color))) 255)))))
In this laboratory, we will not be working with images (just with colors and with lists), so you need not create an image.
a. Copy the sum
and rgb.filteroutdark
procedures
to your definitions pane.
b. Copy the rgb.dark?
and rgb.brightness
procedures
to your definitions pane.
c. Create a list of a dozen or so colors (red, black, green, blue, yellow,
orange, magenta, white, black, etc.). Name it mycolors
.
a. Read through sum
so that you have a sense of its
purpose.
b. Verify that sum
produces the same result as in the
corresponding reading.
c. What value do you expect sum
to produce for the empty
list? Check your answer experimentally.
d. What value do you expect sum
to produce for a singleton
list? Check your answer experimentally.
e. Try sum
for a few other lists, too.
a. Read through the definition of rgb.filteroutdark
to
try to understand what it does.
b. Determine which colors in mycolors
are dark with
(map rgb.dark? mycolors)
.
c. Create a list of nondark colors with (rgb.filteroutdark mycolors)
.
d. Verify that all the resulting colors are not dark.
Suppose the length
procedure were not defined. We could
define it by recursing through the list, counting 1 for each value in the
list. In some sense, this is much like the definition of sum
,
except that we use the value 1 rather than the value at each spot.
a. Using this idea, write a procedure, (mylength lst)
that finds the length of a list (without using length
).
b. Check your answer.
Write a procedure, (product nums)
, that, given a list
of numbers, computes the product of those numbers. You should feel free to use
sum
as a template. However, you should think carefully about
the base case.
What if we don't want to count every value in a list? For example, what if we only want to count the dark values in a list of colors. In this case, we still recurse through the list, but we sometimes count 1 (when the color is dark) and sometimes count 1 (when the color is not dark).
a. Using this idea, write a procedure, (rgb.tallydark colors)
, that, given a list of colors, counts how many are dark.
b. Test your procedure.
In the past, we've found it useful to find the average of two colors. Let's
consider how we might find the average of a list of colors. First, we
would need to find the number of colors in the list. That's easy, we just
use the length
procedure. Next, we need to find the sum of
each component. That's a bit harder, but let's suppose we can do it.
We next divide each sum by the length, and get the average of
that component. Finally, we put it all together with rgb.new
.
That is, we might write
(define averagecolor (lambda (colors) (rgb.new (/ (rgblist.sumred colors) (length colors)) (/ (rgblist.sumgreen colors) (length colors)) (/ (rgblist.sumblue colors) (length colors)))))
Of course, for this to work, we need to write rgblist.sumred
,
rgblist.sumblue
, and rgblist.sumgreen
. For
now, we'll write one of the three. (The other two should be obvious.)
a. Write a procedure, (rgblist.sumred colors)
, that computes
the sum of the red components in a color.
b. Test your procedure on a list of a single color.
c. Test your procedure on the mycolors
list you wrote earlier.
d. It is possible to write rgblist.sumred
without using
direct recursion. How? By an appropriate combination of map
and sum
. Try doing so. (If you can't find a solution,
look at the notes on the problem.)
Write a procedure, (rgblist.filterreds colors)
, that
filters out all elements of colors with a red component of at
least 128.
Write a procedure, (spots.bound spots left top right bottom)
, that filters out all elements of spots
which do not appear in the rectangle bounded at the left by left, at the top by top, at the right by right, and at the bottom by
bottom.
For example, if left is 5, top is 10, right is 8, and bottom is 20, the procedure should remove any spots whose column is less than 5 or more than 8 or whose row is less than 10 or more than 20.
We can use map
to extract the red component of each color.
(map rgb.red colors)
That gives us a list of numbers, which we can sum with sum
.
(sum (map rgb.red colors))
Putting it all together in a procedure
(define rgblist.sumred (lambda (colors) (sum (map rgb.red colors))))
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Labs/recursionbasics.html
.
[Skip to Body]
Primary:
[Front Door]
[Glance]

[Academic Honesty]
[Instructions]
Current:
[Outline]
[EBoard]
[Reading]
[Lab]
[Assignment]
Groupings:
[Assignments]
[EBoards]
[Examples]
[Exams]
[Handouts]
[Labs]
[Outlines]
[Projects]
[Readings]
[Reference]
Reference:
[Scheme Report (R5RS)]
[Scheme Reference]
[DrScheme Manual]
Related Courses:
[CSC151.01 2007F (Davis)]
[CSC151 2007S (Rebelsky)]
[CSCS151 2005S (Stone)]
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 Mon Dec 3 09:55:31 2007.
The source to the document was last modified on Fri Sep 28 10:40:55 2007.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2007F/Labs/recursionbasicslab.html
.
You may wish to validate this document's HTML ; ;
Samuel A. Rebelsky, rebelsky@grinnell.eduhttp://creativecommons.org/licenses/bync/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.