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,
(tally-skips lst), that
takes one argument, a list, and determines how many times the symbol
skip occurs in the list.
For example,
> (tally-skips (list 'hop 'skip 'jump 'skip 'and 'skip 'again))
3
Define and test a Scheme procedure,
(remove-skips 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.)
> (remove-skips (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 skips, 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,
(tally-occurrences 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?
> (tally-occurrences 'apple (list 'pear 'apple 'cranberry 'banana 'apple))
2
> (tally-occurrences '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, (tally-odds values), that
returns the number of odd numbers in a list. For example,
> (tally-odds (list 1 2 3 4 5))
3
> (tally-odds null)
0
> (tally-odds (list 2 4 6 8 10))
0
> (tally-odds (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,
> (tally-odds (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 non-empty 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)
Note that gaps always returns a list one element shorter than the one
it is given.
Hint: What is the base case?
Define and test a Scheme predicate,
(all-in-range? values), that takes a
list as argument and determines whether all of its elements are in the
range from 0 to 100, inclusive.
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
Define and test a Scheme procedure, (types lst),
that takes a list as an argument and returns a list of the types of the
individual elements.
For example,
> (types (list 34 'a (list 1 2 3)))
(number symbol list)
> (types null)
()
> (types (list 'a 'b 'c))
(symbol symbol symbol)
You may want to use your type procedure from a previous
lab.
Some of you have criticized the built-in length method
for counting only the number of values in the top-level list. Write
a procedure, count-values that counts the total number
of non-list values in a list or its sublists.
For example,
> (count-values (list 'a 'b 'c))
3
> (count-values null)
0
> (count-values (list (list 1 2 3 (list 4 5)) (list 'a 'b) (list (list 2))))
8
> (count-values (list null null null null))
0
;
;
Check with Bobby