COMP 210 Homework #3

Fall 2002

Due Mon., Sept. 16. at the start of class

Read Sections 9-15 in the H.T.D.P. book.

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

(25 pts total) Programs on Lists

First, write down a data definition for lists of numbers, and examples of lists of numbers, and a single template for a list-of-number processing function. Then, develop the following programs that consume a list of real numbers:
1. (5 pts) A function sum that returns the sum of all the numbers in the list.
2. (5 pts) A function any-negative? that returns true if and only if ("iff") there is some negative number in the list.
3. (5 pts) A function all-nonnegative?, which returns true iff every number in the list is zero or positive.
  Hint: use the function you just wrote. This might be even easier than modifying the template.
4. (10 pts) A function count-multiples that returns the number of multiples of a given number in the list. Hint: use the built-in function modulo (or equivalently, remainder).
```
; (only) one example of calling count-multiples:
(count-multiples 3 (cons 6 (cons 1901 (cons 7 (cons 2001 empty)))))
2    ; Since 6 and 2001 are multiples 3, but nothing else in the list is.
```
(15 pts total) Functions returning lists
Note: We have yet to provide an example of a function which returns a list. So we'll defer the following problems (in teal) for now. [This update added Sept.13 (fri) 11:00.]
(Although, these exercises are not fundamentally different from other functions processing a list; feel free to give them a go right now, if you like! Regardless, we'll turn them in later.)
1. (5 pts) A function map-square which consumes a list of numbers, and returns a list of the squares of those numbers.
  (The name "map" is traditional, coming from the math sense: a function mapping a bunch of inputs to a bunch of outputs.)
2. (10 pts) A function substitute-num which takes in a list-of-numbers, plus a "before" number and "after" number and returns a list like the input, except that wherever the input list contains the "before" number, the output list now contains the "after" number.
```
; (only) one example of calling susbtitute-num:
(substitute-num 1901 2001 (cons 6 (cons 1901 (cons 7 (cons 2001 empty)))))
(cons 6 (cons 2001 (cons 7 (cons 2001 empty))))
```
(30 pts) Telephone Directory

Once a year, the local telephone company publishes a directory. For our purposes, the directory is a list of entries. An entry consists of a symbol, called the key, and a phone number, represented as a number. A key-data pair such as an entry is called a "tuple" is CS-ese. The directory is often called an "association list" or a "dictionary".

Note: when talking about types of data, this class is precise. Thus be aware that, for this problem, directory and entry are technical terms, each used exactly where intended.
1. (5 pts) Write out the data definitions, examples, and template pertaining to this simple online phone directory. You should have one data definition for entries, and a second data definition for directories.
2. ( 5 pts) Write a program lookup that consumes a symbol and a phone directory and should examine the list for a key that matches the symbol given as input. If it finds a matching key, it returns the matching entry. If no matching entry is found, it returns false.
3. (10 pts) What, exactly, is the type of data returned by lookup? Write a quick data definition for it.
  
  Write lookup-elvis, which takes in a directory, and returns either Elvis's number in the directory, or 'not-found if Elvis isn't listed).
  Hint: use lookup. Note that once you do so, the more pertinent data template is the type returned by lookup, instead of the template for directories, in this case.
4. Deferred -- See note above.
  (10 pts) Finally, let's make a variation of substitute which operates on directories. We'll call it update, and it takes in a directory, a name, and a number. It returns a new directory with all the original entries, plus an entry with the given name/number. If that name already occurred in some entry (with possibly a different number), then the new directory should contain the udpated information, but you should not introduce any duplicate entries. (If you were given a directory that already had duplicate entries for the key you are updating, mention whether your code leaves them be, or eliminates them. (Either is fine.))
Be sure to create a reasonable set of test data and enter it in the definitions window of DrScheme.

For more help (sort of) look up "assoc" in the help desk. No, you cannot use the built-in assoc function!

Note: The fact that the second part of an entry is a number was irrelevant to lookup; we could actually allow any type of data to be associated with a key -- a symbol, a structure, or even another list (perhaps, you have a "meta-directory", where each person has their own personal directory ... or even their own list of directories!). (Slow down, breathe, and re-read that; it takes a moment to think it through.)
To ponder (no response required): Why did we ask to return the entire key/datum entry -- wouldn't it be more convenient to just return the associated datum? (What would be problematic about this?)

(70 er, 45 pts total)