Functional Problem Solving (CSC 151 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: In this laboratory, you will continue to explore the use of recursion.
a. Make a copy of list-recursion-revisited-lab.rkt
, which contains useful definitions
for this lab.
b. Review the file to see what procedures and values are in the list.
How can we find the largest value in the list of numbers? As you've
seen, (
computes the largest of max
val1
val2
)val1
and
val2
. We want to generalize this procedure to
work with a list of values.
Write (
, a procedure that computes the largest value in a list of real numbers
largest
vals
)
To be as general as possible, your implementation of
largest
should handle negative as well as positive
numbers.
>
(largest (list 1 2 3 4))
4
>
(largest (list 1 10 5 6.333 0))
10
>
(largest (list -5 -10 -1 -99))
-1
You may recall that the procedure append
takes as parameters two lists, and joins the two lists together.
Let's generalize that procedure so that it works with more than
two lists.
a. Write a procedure, lists-join
, that,
given a nonempty list of lists as a parameter, joins the member lists together
using append
.
>
(list (list 1 2 3))
((1 2 3))
>
(lists-join (list (list 1 2 3)))
(1 2 3)
>
(list (list 1 2 3) (list 10 11 12))
((1 2 3) (10 11 12))
>
(lists-join (list (list 1 2 3) (list 10 11 12)))
(1 2 3 10 11 12)
>
(list (list 1 2 3) (list 10 11 12) (list 20 21))
((1 2 3) (10 11 12) (20 21))
>
(lists-join (list (list 1 2 3) (list 10 11 12) (list 20 21)))
(1 2 3 10 11 12 20 21)
>
(list null (list 1 2 3))
(() (1 2 3))
>
(lists-join (list null (list 1 2 3)))
(1 2 3)
>
(list (list 1 2 3) null)
((1 2 3) ())
>
(lists-join (list (list 1 2 3) null))
(1 2 3)
>
(lists-join (list null (list 1 2 3) null null null null (list 100 99 98) null))
(1 2 3 100 99 98)
Note: At first glance, it may be puzzling to work with a list of lists. However, you can disassemble that list just as you do any other list: the car of a list-of-lists is a list, the cdr of a list-of-lists is a list-of-lists, but with the first list removed.
Hint: Think about when you have a base case, what
you do in the base case, and what to do with the result of the recursive
case. (Remember, append
is generally used to join
two lists.)
b. Use lists-join
to join some of the color lists
your created in the preliminaries.
Here are possible answers for exercises 1 and 2.
(define largest (lambda (lst) (if (null? (cdr lst)) (car lst) (max (car lst) (largest (cdr lst)))))) (define lists-join (lambda (lst) (if (null? (cdr lst)) (car lst) (append (car lst) (lists-join (cdr lst))))))
You'll notice that both do a similar thing: They take a two-parameter
procedure (max
or append
)
and generalize it to a list of values. The process of repeatedly
applying a two-parameter procedure so as to process a list is
often called folding the procedure.
You'll also notice that they both lists-join
and
largest
use similar code. When we identify a
common structure for similar procedures, it can be helpful to
generalize and then to explore that generalization. You will do
so in this exercise.
a. Sketch a template of the common parts of lists-join
and largest
(with blanks to fill in for the rest).
b. Identify one or two other procedures from the reading that follow the same pattern.
c. Using your template, write a procedure,
(
,
that finds the smallest value in a list.
smallest
lst
)
d. Using your template, write a procedure,
(
,
that finds the darkest color in a list of RGB colors.
irgb-darkest
lst
)
Hint: You may find
it useful to build a utility procedure,
(
,
that finds the darker of two colors.
irgb-darker-of
irgb1
irgb2
)
You may recall that in the reading we explored ways to build predicates that apply to lists by starting with predicates that apply to individual values. Let's try writing a few such procedures.
a. Write a procedure, (
, that, given a list of RGB colors,
determines if all of the colors are bright.
irgb-all-bright?
colors
)
b. Write a procedure, (
, that, given a list of RGB colors,
determines if any of them are bright.
irgb-any-bright?
colors
)
It is often useful to ask whether a list contains a particular
item. In fact, the standard Scheme procedure
member
and the MediaScheme procedure
member?
both do this. Let's write our own
predicate, (
that
holds only when list-contains?
val
vals
)val
appears in
vals
.
We know that
val
does not appear in the empty list.
val
appears in a non-empty
vals
if val
is the
car of vals
or if it appears in the
cdr of vals
.
a. Translate this description into Scheme. That is, write
list-contains?
.
b. We can use list-contains?
to define the following
interesting procedure.
(define greenish? (lambda (color) (list-contains? color greens)))
Explain what this procedure does.
c. What result do you expect from the following expressions?
>
(map greenish? greens)
>
(map greenish? my-colors)
>
(map greenish? (list (irgb 0 0 0) (irgb 255 0 0) (irgb 128 0 0)))
e. Check your answers experimentally.
Using your template from Exercise 3, write a procedure,
(
, that finds the darkest color in
a list of color names. (You'll need to convert color names to
integer-encoded RGB colors in order to compare them. However, you
should return a color name, not an RGB color.)
color-name-darkest
lst
)
Hint: Again, you'll find it useful to write a utility procedure, such
as color-name-darker
.
Using your template from Exercise 3, write a procedure,
(
, that, given a list of positive
and negative numbers, finds the number in the list closest to zero.
closest-to-zero
lst
)
We've seen how to average two colors and a list of colors. But what if we want to do something different: Given a list of colors, we want averages, but only of neighboring elements in the list.
Write a procedure, (
, that, given a list of colors,
computes a new list of colors, by averaging subsequent pairs of
colors. For example, if the input list is the standard seven
rainbow colors (red, orange, yellow, green, blue, indigo, and violet),
the output list will consist of
a red-orange average, an orange-yellow average, a yellow-green
average, a green-blue average, a blue-indigo average, and an
indigo-violet average.
irgb-averages
colors
)
Once again, the length of the result list is one less than the length of the input list.
Define and carefully test a Scheme procedure,
(
,
that takes a list as
argument and returns a list of two lists, one comprising the elements in
even-numbered positions in the given list, the other comprising the
elements in odd-numbered-positions. For example:
unriffle
lst
)
>
(unriffle (list 'a 'b 'c 'd 'e 'f 'g 'h 'i))
((a c e g i) (b d f h))
>
(unriffle null)
(() ())
>
(unriffle (list 'a))
((a) ())
>
(unriffle (list 'a 'b))
((a) (b))