Due: 8:00 a.m., Friday, 5 October 2007
No extensions!
Summary: In this assignment, you will further practice the design of recursive procedures.
Purposes: To give you more experience with a variety of styles of recursion over lists.
Expected Time: Two to four hours.
Collaboration: I encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Submitting: Email me your answer. More details below.
Warning: So that this assignment is a learning experience for everyone, I may spend class time publicly critiquing your work.
Contents:
There are six problems on this assignment. This is because it is helpful to have lots of practice when you are learning to write recursive procedures. One of my colleagues likes to say that your first 30 recursive procedures are the hardest.
The problems are not necessarily in order of difficulty. If you get stuck on one problem, try going on to do another.
You will find the following definitions from the lab on list iteration useful.
(define spot.new
(lambda (col row color)
(list col row color)))
(define spot.col
(lambda (spot)
(car spot)))
(define spot.row
(lambda (spot)
(cadr spot)))
(define spot.color
(lambda (spot)
(caddr spot)))
Suppose the reverse procedure were not included in Scheme.
Could you write it yourself? Certainly! It should be possible to
implement reverse recursively.
One strategy is to use the standard recursive formulation:
(define my-reverse
(lambda (lst)
(if (null? lst)
base-case
(combine (car lst) (my-reverse (cdr lst))))))
Finish this implementation. I suggest you test your implementation on lists of numbers.
When using this strategy, you'll need to think about the question
Suppose I've reversed the cdr of a list. What do I do with the
car to get the reversal of the complete list?
Of course, you've seen more than one strategy for writing recursive
procedures. Another possibility is to use a helper that includes a
what I've done so far
parameter. For example,
(define my-other-reverse
(lambda (lst)
(my-other-reverse-helper null lst)))
(define my-other-reverse-helper
(lambda (reversed-so-far remaining-elements)
(if (null? remaining-elements)
base-case
(my-other-reverse-helper (modify reversed-so-far)
(cdr remaining-elements)))))
Finish this implementation.
Define and test a Scheme predicate, (all-rgb? values),
that takes a
list as argument and determines whether all of its elements are rgb colors, as determined by the rgb? predicate.
For example,
> (all-rgb? (list color.red color.blue color.green))
#t
> (all-rgb? (list "red" color.red))
#f
> (all-rgb? (list color.red color.blue pi 3.2 color.green))
#f
> (all-rgb? (list 1 2 3))
#t
Define and test a Scheme predicate, (all-spots? values),
that takes a
list as argument and determines whether all of its elements are spots.
Recall that a spot is a list consisting of three elements: a column (an
integer), a row (also an integer), and an rgb color.
For example,
> (all-spots? (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
#t
> (all-spots? (list "See Spot run."
(spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
#f
> (all-spots? (list (spot.new 0 0 color.red)
(spot.new 0 1 "blue")
(spot.new 0 2 color.green)))
#f
> (all-spots? (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2.01 color.green)))
#f
> (all-spots? (list (list 0 0 0)
(list 1 1 1)
(list 2 2 2)))
#t
As a hint, you may wish to define a predicate (spot? value) that tests whether a value is a valid spot. You will also find this predicate useful for the next problem.
Write a procedure, (just-spots values), that filters out all elements of values that are not valid spots.
For example,
> (just-spots (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
((0 0 -16776961) (0 1 65535) (0 2 16711935))
> (just-spots (list "See Spot run."
(spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
((0 0 -16776961) (0 1 65535) (0 2 16711935))
> (just-spots (list (spot.new 0 0 color.red)
(spot.new 0 1 "blue")
(spot.new 0 2 color.green)))
((0 0 -16776961) (0 2 16711935))
> (just-spots (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2.01 color.green)))
((0 0 -16776961) (0 1 65535))
> (just-spots (list (list 0 0 0)
(list 1 1 1)
(list 2 2 2)))
((0 0 0) (1 1 1) (2 2 2))
Define and test a Scheme predicate, (member? value lst), that takes two
arguments, a value and a list, and determines whether the given value
appears within the given list. (Hint: use the equal?
predicate to test whether the value is equal to any of the members of
the list. Think about what your procedure should return for the base
case.)
For example,
> (member? color.black (list color.red color.green color.blue color.black color.white))
#t
> (member? color.yellow (list color.red color.green color.blue color.black color.white))
#f
> (member? "red" (list color.red color.green color.blue color.black color.white))
#f
> (member? -1 (list color.red color.green color.blue color.black color.white))
#t
> (member? (spot.new 0 1 color.blue) (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
#t
> (member? (spot.new 0 1 color.teal) (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
#f
> (member? (spot.new 1 1 color.blue) (list (spot.new 0 0 color.red)
(spot.new 0 1 color.blue)
(spot.new 0 2 color.green)))
#f
I will primarily look to see that your code is correct and uses appropriate style. I may reward particularly elegant or well-crafted code with a PLUS, as well as creative extensions of the required work.
Please submit this work via email. The email should be titled CSC151 HW9 and should contain your answers to all parts of this assignment.
Please send your procedure definitions as the body of an email message.
Janet Davis (davisjan@cs.grinnell.edu)
Created October 2, 2007