CS 30 Homework 1
Due by the beginning of class Tuesday, September 10
Finish reading The Little Schemer Chapters 1-3. Then write and test
the following Scheme functions. Remember to think recursively. As a
reminder, here is the approach we discussed in class today for solving a
problem recursively:
Solving a problem recursively means using the problem solution itself as part
of the solution.
- Solve the simplest possible version of your problem directly. The solution
to this "base case" should be obvious (no thinking required).
- For the general case, reduce the problem to a slightly smaller
version of the same problem. Assume that this smaller problem can be
solved "by magic".
- Use the smaller problem's solution to construct a solution to the original
problem.
- (copies n x) takes a number n and any value
x and returns a list containing n copies of x.
Examples:
- (copies 3 'practice) => (practice practice practice)
- (copies 1 42) => (42)
- (copies 0 'whatever) => ()
- (count a lat) takes an atom a and a list of atoms
lat and returns the number of times a appears in
lat. Examples:
- (count 'yes '(oh yes yes yes)) => 3
- (count 'yes '(oh no no no)) => 0
- (count 'no '()) => 0
- (rac ls) takes a non-empty list ls and
returns the last item in the list (rac is the "mirror image" of
car). Examples:
- (rac '(a b c d e)) => e
- (rac '(apple)) => apple
- (rac '(banana (mango shake (yum yum))))
=> (mango shake (yum yum))
- (rdc ls) takes a non-empty list ls and
returns all of the items except the last (rdc is the "mirror image" of
cdr). Examples:
- (rdc '(a b c d e)) => (a b c d)
- (rdc '(apple)) => ()
- (rdc '(banana (mango shake (yum yum))))
=> (banana)
- (snoc x ls) takes any value x and a list
ls, and returns a new list with x added to the end of
ls (snoc is the "mirror image" of cons). Examples:
- (snoc 'another '(a b c d e)) => (a b c d e another)
- (snoc 'sauce '(pepperoni pizza)) => (pepperoni pizza sauce)
- (snoc 'whatever '()) => (whatever)
- (reverse lat) takes a list of atoms lat and
returns a new list with all of the atoms in reverse order. Hint: use
snoc in your definition of reverse. Examples:
- (reverse '(a b c d e)) => (e d c b a)
- (reverse '(hello goodbye)) => (goodbye hello)
- (reverse '()) => ()
- (seconds lats) takes a list of lats and returns a
new lat consisting of the second atom from each lat in the list.
Examples:
- (seconds '((paella spanish) (wine red) (and beans)))
=> (spanish red beans)
- (seconds '()) => ()
- (seconds '((red hot) (chili dogs))) => (hot dogs)
- (double a ls) takes an atom a and a list
ls and doubles the first a in ls (it is the converse
of rember, which removes the first a). Examples:
- (double 'hot '()) => ()
- (double 'chili '(cincinnati chili)) => (cincinnati chili chili)
- (double 'hot '(texas hot chili)) => (texas hot hot chili)
Turning in your homework
Put all of your function definitions into a single file called hw1.scm
and bring a hardcopy printout of the file to class with you on Tuesday.