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:

• Follow the design recipe.
• For each group of examples, use the same template, because the functions are on the same kind of data.
• Use the stepper to help understand the programs.

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

First, a quick review of what a list is.

A list is a common data structure for keeping track of an arbitrary amount of information. Lists use all three of the basic building blocks we've seen:

• compound data, as for plane brand descriptions or points,
• cases, as for intervals or colors, and
• recursion.

     ; A list-of-symbols is one of
     ;   - empty
     ;   - (make-lst f r), where f is a symbol, and r is a list-of-symbols
     (define-struct lst (first rest))

• the constructor make-lst,
• the selectors lst-first and lst-rest, and
• the predicates empty? and lst?.

(Note: We sometimes intentionally misspell words like lst to avoid redefining built-in Scheme functions.)

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 f r), where f is a symbol, and r is a list-of-symbols

• the constructor cons,
• the selectors first and rest, and
• the predicates empty? and cons?.

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.

     (define (los-fun a-los)
        (cond
           [(empty? a-los) ...]
           [(cons? a-los)  ...(first a-los)...(los-fun (rest a-los))...]))
     

To do:

1. Make the data definition for lists of numbers.
2. 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. Consider: How many numbers are in (cons 3 (cons 1 empty)), for example?
3. Develop a program which takes a list of numbers and returns the sum of all the numbers.
4. Develop a program which takes a list of numbers and returns the product of all the numbers.

Let's build an example using lists of more interesting data.

To do: First, copy the following into DrScheme:

     ; A database record is
     ;   (make-record name age salary)
     ; where name is a symbol, and age and salary are positive numbers
     (define-struct record (name age salary))

     ; A database is a list of database records, i.e., one of
     ;   - empty
     ;   - (cons f r)
     ;     where f is a database record, r is a database

1. Create an example database.
2. Develop db-count, which takes a database and returns a count of those employees who are older than 22 and earn more than 100000.
3. 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).

To do:

1. Develop a program which consumes a list of numbers and another number and returns a list of the sums of the original list and the second argument. 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.

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.

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.