Comp 210 Lab 3: Lists

This lab is mainly practice with lists. There are too many examples here to do all during lab. Instead, do some from each group during lab, and the rest on your own. We may revisit some of these examples in next week's lab, also.

Important for all examples:

Index: Lists, Design Recipe, Lists of numbers, Databases, Functions resulting in lists, Non-empty lists, Heterogenous lists


Lists

First, a quick review of what a list is.

Using lists is so common that Scheme has these functions built in, except using some different names. Instead, write

     ; A List-of-Symbols is one of
     ;   - empty
     ;   - (cons symbol List-of-Symbols)
and use


Design Recipe

Now, let's quickly review our latest design recipe.

We know our programs should take advantage of the structure of the data. Now that we know about compound (or structured) data, let's use that knowledge in our methodology.

  1. Formulate a data definition.
  2. Make examples of the data.
  3. Write the function's contract, purpose, and header.
  4. Make examples of the function's use.
  5. Make a template for the function body. The template should remind you how to take advantage of the structure in the data definition.

    Q: What are the steps for developing our template?

  6. Write the function body.
  7. Test the function.

A: The template development steps are:

  1. Use a cond expression with the same number of clauses as the data definition has cases. Use the appropriate predicates in tests for each case. (If the data definition has only one case, skip the cond.)
  2. In each case, show the uses of selectors.
  3. In each case, show the uses of natural recursion.
For example, the template for a function on List-of-Symbols is
     ;; los-fun: List-of-Symbol --> ??
     ;; A fun(ction) template.
     ;;
     (define (los-fun a-los)
        (cond
           [(empty? a-los) ..]
           [(cons? a-los)  ..(first a-los)..(los-fun (rest a-los))..]))
     


Lists of numbers

To do:

  1. Make the data definition for List-of-Numbers. (Extremely similar to List-of-Symbol.)
  2. Make some examples of List-of-Numbers.
  3. Make the template for List-of-Numbers. Make sure you understand what each step of the design recipe wants.
  4. Develop a program which takes a List-of-Numbers and returns the length of the list, i.e., a count of the items in the list. (Of course, also first make some test cases, e.g. How many numbers are in (cons 3 (cons 1 empty))?)
  5. Once your function works, use the stepper with a friend, and step through the program on a list of length 2. How many times is your function called (counting both the initial call plus recursive calls)?
  6. Develop a program which takes a List-of-Numbers and returns the sum of all the numbers. (Yes, this includes test cases. We'll stop reminding you now.)
  7. Develop a program which takes a List-of-Numbers and returns the product of all the numbers.


Databases

With a friend, let's build an example using lists of more interesting data. This just uses ideas you've already learned, but in new contexts. Stick to the design recipe, to avoid confusion!

To do: First, copy the following into DrScheme:

(define-struct record (name age salary))
;
; A record is
;   (make-record symbol num num)

; A database is a list of database records, i.e., either
;   - empty
;   - (cons record database)
(Note the meaning of the above fonts, when making examples of the data: In "(make-record symbol ..)", you replace symbol with some particular symbol, but the (make-record and ) you copy literally.)
  1. Create some example records (not databases -- just records).
  2. Create a template for records.
  3. Write the function eligible?, which takes in a single record, and returns whether or not it represents somebody who earns more than 60000 and is younger than 53.
  4. Create an example database.
  5. Write the template for functions which handle entire databases.
  6. Develop number-eligible, which takes a database and returns a count of those employees who are younger than 53 and earn more than 60000.
  7. For the curious... Develop db-search, which takes a database and returns a list of those employees' names (in the order they appear in the database).


Functions returning lists

To do:

  1. Develop a program which consumes a list of numbers and another number n, and returns a list where each element is n bigger. E.g.,
         (add-numbers (cons 1 (cons 3 (cons 4 empty))) 2)
         =
         (cons 3 (cons 5 (cons 6 empty)))
         
  2. Develop a program which consumes a list of numbers and returns a list of all of those numbers which are positive.


For the curious...Mixed data (heterogenous) lists

To do:

  1. Make a data definition for a value which is a symbol or a number.
  2. Make a data definition for lists containing symbols and/or numbers. Examples would include
         empty
         (cons 1 (cons 5 (cons 0 empty)))
         (cons 1 (cons 'hi empty))
         (cons 'hello (cons 'there empty))
         
  3. Develop a program which computes the product of all the numbers in a such a list. The structure of your program should correspond with your choice of data definition.
Note: There are two reasonable ways to do this, although we hinted at the usually preferable one.


For the curious...Non-empty lists

To do:

  1. Make a data definition for non-empty lists of numbers. Hint: The base case should not be empty, since that is not a non-empty list of numbers! What is a description of the shortest non-empty lists of numbers?
  2. Develop a program which takes a non-empty list of numbers and returns the average (aka, arithmetic mean) of all the numbers.
  3. Develop a program which takes a list of numbers and returns the average of all the numbers. For this example, arbitrarily define the average of an empty list to be false.
Note: There are actually two reasonable solutions to this, although we hinted towards the usually preferable one.