Practice Questions #2
In the following problems, you are asked to define short procedures.
All of your procedures should be true functions, without side effects.
(That is, you won't need the special form set!, or the procedures
set-car! or set-cdr!)
This implies that you will not need to use begin, because begin is
only necessary for writing sequences where the order of side-effects
matters. Likewise, it also implies that you will never need more than
one expression in the body of a procedure.
Several of the problems require iterating through a list, but in all
cases you should use recursion to perform this iteration.
Some of your procedures will be very similar to procedures you've
seen in the class notes, or on the board in class. Try to write
these procedures without just copying the solutions you've seen
before---you should understand *why* you're doing what you're
doing. You should try out your answers in a real Scheme system.
If you get stuck, then consult your notes, and make sure you understand
whatever you didn't understand before. You'll have to solve similar
problems in graded homework and tests, so the point here is to learn
how to do things.
For problems involving lists and recursion, it's a very good idea
to work through some examples on paper, drawing box-and-arrow
pictures of the lists and stepping through your procedure's
operation.
After you've written your answer and are satisfied with it---or
if you get really stuck, even with the help of your notes---look
at my answers and comments.
Be sure to read the comments even if you get the answer right, and pay
attention to indenting. There are important points about programming
style in the comments.
In quizzes and homework, you will be graded on indenting---not much, but
a little, because indenting is important, and if I'm misled by your
indenting, I may think your answer is incorrect anyway.
General advice on programming:
Write small procedures, usually no more than a dozen lines and often
only one to five lines. If you're writing lots of big procedures,
you're not breaking the problems down logically.
When writing recursive procedures, think about the base cases and
the recursive steps. For recursion over lists, the base case is usually
when you hit a null pointer. For recursion over trees, the base cases
are whatever kinds of things are at the leaves of the trees.
Write the base cases first, and test them first. This will help avoid
infinite recursion problems, and remind you to write the base cases. (If
you don't write and test the base cases first, you're likely to mess them
up or forget them entirely, and feel a little foolish when your procedure
gets stuck in an infinite recursion.)
When you run your program, test the low-level procedures first.
This is really easy in Scheme, because you can do it interactively
and type in data structures as literals, using quotation.
Then try out the higher-level procedures that depend on the lower
level procedures you've tested.
---
1. Define a procedure add5, which takes an argument n, which is expected
to be a number, and returns a value that is 5 greater than n. Use
the procedure + and no others. Use the normal procedure definition
syntax.
Example use: (add5 7) => 12
(remember, => means "evaluates to")
Hint: This is just a trivial procedure definition to make sure you
know the normal syntax of procedure definitions.
2. Rewrite the procedure definition in #1 using plain variable definition
syntax and lambda.
Hint: this is really, really easy if you understand that procedures
are anonymous, lambda means "make procedure", and the "name"
of a procedure is really just the name of a variabe whose
value points to the procedure.
3. Define two procedures, first and rest, each of which takes an argument
named lis, which is a list. first returns the first item in the list
lis. rest returns a list of the rest of the items in lis, i.e, all but
the first. Assume that the arguments passed to these procedures are
non-empty lists.
Example uses: (first '(foo bar baz)) => foo
(rest '(foo bar baz)) => (bar baz)
Hint: this is really, really, really easy.
4. Define a procedure last, which returns the last element of a proper,
non-null list.
Example uses: (last '(foo 22 bar 19 baz)) => baz
(last '(1 2 3)) => 3
(last '(a)) => a
(last '()) is an error
Hint: this is a somewhat like length (in the Scheme notes), in that
we need to recurse down a list to the end. It's different from
length, though, and easier, because we don't need to sum the
list on the way back up from the recursion---we just return
whatever we find at the end of the list.
5. Define a procedure double-all, which takes one argument, lis, which
is a list of numbers, and returns a list of numbers where each number
is twice the number in the corresponding position in the original list.
Example use: (double-all '(5 8 3)) => (10 16 6)
Hint: this is a lot like list-copy in the Scheme notes, except
that we don't use the car of the list as-is.
6. Define a procedure list-product, which gives the product of the numbers
in a list of numbers. For a null list, return 1. For a list of one
item, return that item.
Example uses: (list-product '(1 2 3)) => 6
(list-product '(500 10 5 1)) => 25000
(list-product '(5 2)) => 10
(list-product '(2)) => 2
(list-product '()) => 1
Hint: this is a lot like list-sum in the Scheme notes, except
that for a zero-element list, we return 1, the identity
value for multiplication, rather than 0, the identity
value for addition.
7. Define a procedure remove-first which takes two arguments, val and list,
where val is any value and lis is a (proper) list, and returns a new
list which has the same elements as the original list, except that the
first occurrence of the value val in the original list is missing from
the new list. Use eqv? to check whether an element of the original list
is "the same as" val. If there's no occurrence of val in lis,
remove-first should return a copy of the original list.
Example uses: (remove-first 2 '(3 2 5 3 1 2)) => (3 5 3 1 2)
(remove-first 'foo '(bar baz quux foo)) => (bar baz quux)
(remove-first 'bar '()) => '()
(remove-first 'baz '(foo bleen)) => (foo bleen)
Hint: this is a lot like list-copy, in that we need to construct
a modified copy of a list, but it's also like append, in that
we can use the "rest" of the list as-is, once we've gotten
to the point where the new list is different from the old one.
8. Define a procedure count-occurrences, which takes two arguments, val
and lis, and searches the list lis for the value val, counting the
number of times the value val occurs in the list lis. Use eqv?
as the test for whether a list item is the same as the value we're
counting occurrences of.
Hint: this is a lot like length (in the Scheme notes), in that
we recurse through a list to the end, and sum things on the
way back up from the recursion.
Example uses: (count-occurrences 'foo '(bar 1 foobaz 1 bar foo))
=> 2
(count-occurrences '3 '(5 6 3 foo 2 1))
=> 1
9. Define a procedure remove-all which takes arguments val and lis, where
val is any value and lis is a (proper) list, and returns a new list which
has the same elements as lis, except that all occurrences of the value
val in the original list are missing from the new list. Use eqv?
to test whether each value in the list is "the same" as the value
we're removing.
Hint: this is a lot like list-copy, except that we need to skip
items that match (are eqv? to) the target value, val.
Example uses: (remove-all 2 '(3 2 5 3 1 2)) => (3 5 3 1)
(remove-all 'foo '(bar foo baz foo bar)) => (bar baz bar)
(remove-all 6 '(6 6 6)) => ()
10. Define a procedure list-tree-sum, which is like pair-tree-sum (from
the Scheme notes), in that it sums all of the numbers in a tree.
For a number (a leaf in the tree), list-tree-sum should return
that number. For a list, it should return the list-tree-sum of all
of the items in the list.
Unlike pair-tree sum, your procedure list-tree-sum should ONLY work
on proper lists (and plain numbers). i.e., if the cdr of a pair
is not a pair or the empty list, an error should be signaled.
Your procedure should also signal an error if any of the elements
of a list (i.e., the car values of the pairs) is null.
Examples: (list-tree-sum 2) => 2
(list-tree-sum '(1 3 2)) => 6
(list-tree-sum '((1 2) 3 (4 (5 (6))))) => 21
(list-tree-sum '(1 . 2)) is an error
Hints: This is rather like the postfix-display problem from
the first quiz, but with some differences. You do want
to consider each list at a given level as though it
were a single object, for purposes of the overall
recursion. On the other hand, since each of the lists
that acts as a tree node can be of any length, you
*also* need to use recursion to iterate over each
list. Your code should therefore use recursion in
two different ways.
That is, you mostly want to think of lists as though
they were single objects, like records, in designing the
overall recursion. So one of your uses of recursion should
implement normal tree-traversal recursion. When you want to
operate on all of the children of a list, then you need to
rely on the fact that a list is really a sequence of pairs
strung together by the cdrs, and do simple list-traversal
recursion over that list.
You can ensure that an error will be raised for an improper
list if you always take the cdr of anything that's supposed
to be a pair. You can check for null, and take the cdr
of every non-null list, and cdr will signal an error if
it's ever given a non-pair.
Write one procedure, list-tree-sum, that traverses the tree
of lists, using another procedure, node-sum, that iterates
over the elements of a list at one level in the tree.
Each of these procedures should only be a few lines long.
If it's longer, you're probably doing something unnecessarily
complicated and need to think about the structure of the
problem again.
Notice that the overall tree data structure is recursively
defined. A tree may be either a plain number or a
list of trees. The structure of our routine list-tree-sum
should directly reflect this definition.
Likewise, the structure of a tree node is recursively
defined---it's a list, which is either null or a pair
whose cdr is a list. The structure of your node-sum
routine should directly reflect this, in much the same
way that list-sum reflects the definition of a plain list
of numbers.
These procedures will be mutually recursive.