Fundamentals of Computer Science I (CS151 2003F)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Guidelines for Lab Writeups]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Scheme Report]
[Glimmer Scheme Reference]
[CSC151.01 (Gum)]
[CSC151 2003S]
[CSC151 2002F]
[SamR]
Summary: In a previous laboratory, you experimented with and developed procedures that recurse over lists of numbers. In this laboratory, you will continue your exploration of recursion over lists, focusing on lists of symbols or lists of lists.
Contents:
a. Reflect on the patterns of list recursion you learned in the first lab on recursion and the reading on recursion.
b. Start DrScheme.
Define and test a Scheme procedure,
(tallyskips lst)
, that
takes one argument, a list, and determines how many times the symbol
skip
occurs in the list.
For example,
> (tallyskips (list 'hop 'skip 'jump 'skip 'and 'skip 'again))
3
Define and test a Scheme procedure,
(removeskips lst)
, that
takes a list of symbols as its argument and returns a list that does not
contain the symbol skip
, but is otherwise identical to the
given list. (Use the predicate eq?
to test whether two
symbols are alike.)
> (removeskips (list 'hop 'skip 'jump 'skip 'and 'skip 'again))
(hop jump and again)
The example illustrates the intended effect of the procedure. By itself,
however, it's not an adequate test of your procedure. It would be a good
idea to test the case in which the given list is empty, a case it which it
contains only skip
s, and one in which it contains only symbols
other than skip
. You might also test different positions
opf skip
: at the front, at the end, and in the middle.
We recommend that you test the procedures you create very thoroughly. In most cases, testing does not reveal any errors in your procedures; but finding and correcting the errors that testing exposes is one of the most productive and rewarding uses of a programmer's time.
Define and test a Scheme procedure,
(tallyoccurrences sym symbols)
,
that takes two arguments, a symbol and a list of symbols, and determines
how many times the given symbol occurs in the given list.
Hint: Use direct recursion. Here are the questions that you must resolve: What is the base case? What value should the procedure return in that case? How can you simplify the problem in order to recursively invoke the procedure being defined? What do you need to do with the value of the recursive procedure call in order to obtain the final result?
> (tallyoccurrences 'apple (list 'pear 'apple 'cranberry 'banana 'apple)) 2 > (tallyoccurrences 'apple (list 'oak 'elm 'maple 'spruce 'pine)) 0
Define and test a Scheme procedure,
(lengths lists)
that takes a list
of lists as its argument and returns a list of their lengths:
> (lengths (list (list 'alpha 'beta 'gamma)
(list 'delta)
null
(list 'epsilon 'zeta 'eta 'theta 'iota 'kappa)))
(3 1 0 6)
Write a Scheme procedure, (tallyodds values)
, that
returns the number of odd numbers in a list. For example,
> (tallyodds (list 1 2 3 4 5)) 3 > (tallyodds null) 0 > (tallyodds (list 2 4 6 8 10)) 0 > (tallyodds (list 1 2 1 2 1 1)) 4
If you'd like to be extra careful, make sure that your procedure works correctly even if some of the values in the list are not numbers. For example,
> (tallyodds (list 'one 2 3 4 'five))
1
Write a Scheme procedure, (odds values)
, that, given
a list, produces another list that contains only the odd numbers in the
first list. For example,
> (odds (list 1 2 3 4 5)) (1 3 5) > (odds (list 'one 'two 'three 4 'five)) () > (odds (list (list 1 2 3) (list 4 5 6))) ()
Define and test a Scheme procedure, (gaps values)
,
that takes a nonempty list of real numbers as its argument and returns
a list of the disparities between numbers that are adjacent on the
given list.
> (gaps (list 30 16 21 9 42)) (14 5 12 33) > (gaps (list 1 2)) (1) > (gaps (list 2 1)) (1)
Hint: What is the base case?
Note: The gaps
procedure always returns a list one element shorter than the one it is given.
Define and test a Scheme predicate,
(allinrange? values)
, that takes a
list as argument and determines whether all of its elements are in the
range from 0 to 100, inclusive.
For example,
> (allinrange? (list 40 50 100 10)) #t > (allinrange? (list 40 50 100 10)) #f > (allinrange? (list)) #t
Define and test a Scheme predicate,
(member? sym symbols)
, that takes two
arguments, a symbol and a list, and determines whether the given symbol
appears within the given list.
For example,
> (member? 'a (list 'a 'b 'c)) #t > (member? 'a (list 'b 'c 'b 'd)) #f > (member? 'a (list 'd' 'c 'b 'a)) #t
Develop a Scheme procedure, (riffle lst1 lst2)
, that takes two lists as arguments and returns a list that results from riffling the given lists together, like two halves of a deck of cards: Element 0 of the result list should be element 0 of lst1, element 1 of the result list should be element 0 of lst2, element 2 of the result list should be element 1 of lst1, element 3 of the result list should be element 1 of lst2, and so on and so forth. Keep taking subsequent elements from alternating lists until the shorter list is exhausted. Once the shorter of the given lists is exhausted, all the rest of the elements of the result list should come from the other list.
> (riffle (list 'a 'b 'c 'd 'e) (list 'x 'y 'z)) (a x b y c z d e) > (riffle null (list 'x 'y 'z)) (x y z) > (riffle (list 'x 'y 'z) null) (x y z) > (riffle (list 'x 'y 'z) (list 'a)) (x a y z) > (riffle (list 'a) (list 'x 'y 'z)) (a x y z)
Note: There are a few ways to approach this problem. The approach you take will be guided by your selection of a base case or cases. In particular, you might choose only one base case (typically, when lst1 is null) or you might choose two base cases (when lst1 is null; when lst2 is null).
It is possible to write the member?
function mentioned above using if
/cond
expressions or by using a combination of and
, or
, and not
.
a. Rewrite member?
using whichever technique you didn't use above.
b. Which solution do you prefer? Why?
The hint for the riffling question above suggests that there are two different solutions to the problem. Write a different solution than the one you first came up with. (If you had one base case, use two. If you had two base cases, use one.)
Some of you have criticized the builtin length
method
for counting only the number of values in the toplevel list. Write
a procedure, countvalues
that counts the total number
of nonlist values in a list or its sublists.
For example,
> (countvalues (list 'a 'b 'c)) 3 > (countvalues null) 0 > (countvalues (list (list 1 2 3 (list 4 5)) (list 'a 'b) (list (list 2)))) 8 > (countvalues (list null null null null)) 0
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/History/Labs/listrecursion.html
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Guidelines for Lab Writeups]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Scheme Report]
[Glimmer Scheme Reference]
[CSC151.01 (Gum)]
[CSC151 2003S]
[CSC151 2002F]
[SamR]
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 Tue Dec 9 13:59:06 2003.
The source to the document was last modified on Tue Sep 23 13:42:37 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003F/Labs/listrecursion.html
.
; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu