This problem requires Lecture 8 and book section 1.2.
Part A - 'union' - (40 minutes)
This function will take two lists and returns a third list which is the union of the elements
of the two lists. Be sure the final list has no duplicate elements. The elements
in the final list may be in any order, so for the first example your function
may return either (a b) or (b a).
> (union '() '(a b a)) (a b) > (union '(x y 7) '(7 z x w)) (x y 7 z w)
Hint: You may find it useful to first define a function that removes duplicate elements from a list. Use that function it in the definition of union.
You may find the function member helpful. The syntax is:(member x lst). If x is in lst, member returns a list containing the first occurence of x and all the elements after it. If x is not in lst, member returns #f. (i.e.: (member 'a '(c b a b c a)) returns the list (a b c a))
These two problems together explore higher-order functions and the power of functional languages.
Part B - 'prod' - (10 minutes)
Write a function called prod that takes a list of numbers and
returns their product. (This should be easy by now.)
Part C - 'fold' - (20 minutes)
If we wanted to also define a function that summed a list of numbers,
we could do that as well, but perhaps a higher-order function (an abstraction)
would do the job in a more general way. Write a function called fold
that generalizes prod. Your function should take an operator, a base
number (what you return for an empty list-- the identity for the
operator), and a list as arguments. For example, to sum a list of numbers
with fold, you would make a call in scheme as:
(fold + 0 '(1 2 3 4 5))
For the product of a list of numbers, you would make a call in scheme as:
(fold * 1 '(1 2 3 4 5))
Try out your fold function by rewriting prod using it.
What does the following code do?
(fold + 0 (fold append '() '((3 1 2) (3 4 5) (3 5 6))))
Try to answer without running the code, then verify your answer.
YOU MUST NAME YOUR FUNCTIONS union, prod, fold.
Instructions on submitting homework is here
Last updated at 11:50 am on Friday, January 03, 2003.