CS 30 Homework 3
Due by the beginning of class Tuesday, September 24
Reading assignment: Chapters 7-8 of The Little Schemer.
Finish the following recursive functions from the last two labs. Don't
hesitate to use helping functions if that would make solving the problem
easier. Make sure to test your programs on a variety of input data to verify
that they work correctly in all cases.
These functions work with flat lists:
- (odd-or-even nums) takes a flat list of numbers and
returns a new list with odd numbers replaced by the symbol odd and
even numbers replaced by the symbol even. Remember that the
built-in Scheme functions odd? and even? are available.
Example:
(odd-or-even '(1 2 3 5 4)) => (odd even odd odd even)
- (count-nums lat) takes a flat list of atoms and tells how
many numbers are in the list. The built-in Scheme function number?
will come in handy here, which returns true given a number, or false
otherwise. Examples:
(count-nums '(a b c 42 d 13 e f 8)) => 3
(count-nums '(x y z)) => 0
- (all-nums? lat) takes a flat list of atoms and returns
true if the list contains only numbers, or false otherwise. The built-in
Scheme function number? will come in handy here. Examples:
(all-nums? '(1 2 3 4)) => #t
(all-nums? '(2 b or not 2 b)) => #f
- (index sym lat) takes a symbol sym and a flat
list of symbols lat and returns the index number of the first
occurrence of sym in lat, counting from zero. If
sym does not appear in the list, then index returns -1.
Examples:
(index 'cs30 '(this class is cs30)) => 3
(index 'mango '(apple banana cherry)) => -1
(index 'hello '(hello goodbye)) => 0
- (insert n nums) takes a number n and a flat list
of numbers in ascending order, and returns a new list with n
inserted into nums at the correct position. Examples:
(insert 5 '(1 3 4 8 9)) => (1 3 4 5 8 9)
(insert 5 '(1 3 5 5 9)) => (1 3 5 5 5 9)
(insert 2 '(6 7 8)) => (2 6 7 8)
(insert 10 '(6 7 8)) => (6 7 8 10)
- (sort nums) takes an unsorted list of numbers and returns
a new list with the numbers sorted into ascending order. Example:
(sort '(8 4 5 1 4 2 7)) => (1 2 4 4 5 7 8)
HINT: To sort a list of numbers, first sort the rest of the numbers, then
insert the first number into the rest at the appropriate location. Think
recursively!
These functions work with arbitrarily-nested lists:
- (odd-or-even* nums) takes a nested list of numbers and
returns a new list with the same nested structure, with odd numbers replaced
by the symbol odd and even numbers replaced by the symbol
even. Example:
(odd-or-even* '((1 2) ((3)) 5 4)) => ((odd even) ((odd)) odd even)
(odd-or-even* '(7 (2 (3 8) 5))) => (odd (even (odd even) odd))
- (count-all* ls) takes an arbitrary nested list and tells
how many items are in the list. Examples:
(count-all* '((3 apple) ((peach 8 6) 9) pie)) => 7
(count-all* '(ginger fred)) => 2
- (count-nums* ls) takes a nested list of atoms and tells
how many numbers are in the list. Examples:
(count-nums* '((3 apple) ((peach 8 6) 9) pie)) => 4
(count-nums* '((apple banana) cherry)) => 0
- (addup-nums* ls) takes a nested list of atoms and adds up
all of the numbers in the list. Examples:
(addup-nums* '((3 apple) ((peach 8 6) 9) pie)) => 26
(addup-nums* '((apple banana) cherry)) => 0
- (swap* s1 s2 ls) takes two symbols s1 and
s2 and a nested list, and returns a new nested list with all
occurrences of the s1 symbol replaced by the s2 symbol, and
vice versa. Examples:
(swap* 'red 'blue '(red (yellow (blue) red)))
=> (blue (yellow (red) blue))
(swap* 'orange 'blue '(((red yellow)) blue red))
=> (((red yellow)) orange red)
- (reverse* ls) takes a nested list and returns a "mirror
image" of the list, with all of its internal structure preserved.
Examples:
(reverse* '(a (b (c (d e))))) => ((((e d) c) b) a)
(reverse* '((a b c d) e f g)) => (g f e (d c b a))
Turning in your homework
Put all of your function definitions into a single file called
hw3.scm and bring a hardcopy printout of the file to class with you
on Tuesday.