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:
Definition and Design Recipe Review,
Lots of Examples
Definition and Design Recipe Review
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:
- cases, as for intervals or colors,
- compound data, as for plane brand descriptions or points, and
- recursion.
Data definition questions
How are lists defined?
What are the constructors, selectors, and predicates?
|
See the definition and functions. |
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.
- Data definition.
- Data examples.
- Function's contract, purpose, and header.
- Function's example uses.
- Function's template.
The template should remind you
how to take advantage of the structure in the data definition.
- Function body.
- Function testing.
Lots of examples
There are many more examples here than you can do in lab.
Labbies can pick and choose what to present.
Students should look over the rest on their own.
Lists of numbers
Series of list-of-numbers exercises
Do at least the first 5 parts in lab:
- Make the data definition for list-of-numbers.
(Extremely similar to list-of-symbols.)
- Make some examples of list-of-numbers.
- Make the template for list-of-numbers.
Make sure you understand what each step of the design recipe wants.
- 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)) ?)
- Once your function works, use the stepper,
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)?
- 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.)
- Develop a program which takes a list-of-numbers and returns the product of
all the numbers.
|
Databases
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!
Series of database exercises
- Copy the following into DrScheme:
; A record is
; (make-record name age salary)
; where name is a symbol, and age and salary are numbers.
(define-struct record (name age salary))
; A database is a list of database records, i.e., either
; - empty
; - (cons f r)
; where f is a record, and r is a database (or, equivalently, a list-of-records).
- Create some example records (not databases -- just records).
- Create a template for records.
- 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.
- Create an example database.
- Write the template for functions which handle entire databases.
- Develop number-eligible, which takes a database and returns
a count of those
employees who are younger than 53 and earn more than 60000.
- 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
Of course, since lists are just another form of data, we can also
return lists from functions.
As always, use the template corresponding to the input (also
lists in these examples), not the output.
Series of exercises
Do at least one of these in lab:
- 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)))
- Develop a program which consumes a list of numbers and returns
a list of all of those numbers which are positive.
|
Mixed data (heterogenous) lists
Sometimes we would like to have multiple kinds of data stored
intermingled within a single list. Technically, these are called
heterogenous lists.
Series of heterogenous list exercises
- Make a data definition for a value which is a symbol or a number.
- 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))
- 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.
|
There are two reasonable ways
to do this, although we hinted at the usually preferable one.
|
Non-empty lists -- Optional
Sometimes we would like to work with lists that are guaranteed to be
non-empty. Rather than just stating this restriction as a side note,
we can encode it into a separate data definition. This allows our
code to be more explicit in what kind of data it uses.
Series of non-empty list exercises
- 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?
- Develop a program which takes a non-empty list of numbers and returns the
average (aka, arithmetic mean) of all the numbers.
- 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.
|
There are actually
two reasonable solutions to this, although
we hinted towards the usually preferable one.
|