COMP 210, Spring 2001
Homework 3
Due Sept.19 (wed), start of class

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.

  1. (6pts) Programs on Lists

    Write down a data definition for lists of numbers, and examples of lists of numbers. Now, develop the following programs that consume a list of real numbers:

    1. A function sum that returns the sum of all the numbers in the list.

    2. A function count-positives that returns the number of positive numbers in the list.

    3. A function any-negative? that returns true if and only if ("iff") there is some negative number in the list.

    4. 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.

  2. (6pts) Functions returning lists

    1. 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. A function substitute-millenium which takes in a List-of-Number, and returns a list like the input, except that wherever the input list contains 2000, the output list contains 2001. (If you prefer, you can instead write the more general substitute, which takes two additional arguments: the before- and after-numbers to substitute.)

  3. (8pts) 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.

    Note: when talking about types of data, this class is precise. Thus be aware that, for this problem, directory and entry are technical terms, used exactly where intended.

    1. 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. Write a program lookup that consumes a symbol and a phone directory and Clarify by deleting this clause: produces a phone number. lookup 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. 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 '411 (if Elvis isn't listed). Update: return a symbol such as 'not-found instead.
      Hint: use lookup. Note that once you do so, the more pertinent data template is the type returned by lookup, instad of the template for directories, in this case.

    4. 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 alrady 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.

    Schemers sometimes call a directory in this form an association list

    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?)

    An aside:
    It turns out, 'dictionary' is a technical term, in computer science -- it is the Abstract Data Type where you insert some value & it's associated key, and later lookup the value by key. E.g., the registrar software may use a dictionary where the key is your student-id, and the associated value is a struct containing all your data.

    So more precisely: an association-list is one possible implementation of a Dictionary. There are other ways of implementing Dictionary (e.g., a list of key/value pairs which is sorted by key. If you go on to take comp212, you'll learn of hash tables, another implementation of Dictionary.)

    We call it an *abstract* data type, because if you write code which uses a Dictionary somebody else wrote (say, in a Teachpack), your code just calls "lookup" and "update" [usually called "insert"]; you could care less what particular implementation the teachpack uses. (More importantly, you can later decide to switch to somebody else's Dictionary teachpack without having to modify one character of your own code.)