If you have not already done so,
please take the quiz before continuing with lab.
Instructions for students & labbies:
Start with short group discussion.
Students use DrScheme on the exercises at their own pace,
while labbies wander among the students, answering questions,
bringing the more important ones to the lab's attention.
- Follow the design recipe, including using templates.
- Use the stepper on at least a few examples.
- It's likely you won't have time to do all the examples during lab.
Students should look over the rest on their own.
Review: List Definition
Questions
Answer/discuss the following as a group.
- What is the data definition of a list of numbers?
- What are the constructors, selectors, and predicates for lists of
numbers?
- What are some examples of lists of numbers?
- What is the template for functions on lists of numbers?
|
|
Template reminder.
|
Lots of Exercises
Exercises: lists of numbers
All of these examples use the same input type: a list of numbers.
So, don't forget to reuse what you can to same yourself time.
Use your data examples (i.e., sample lists of numbers) for each of the
function examples (i.e., what the function does on each of those
inputs).
Copy-and-paste the type's template as your starting point
for each function.
- Develop a program
count-positive
which takes a list of numbers and returns a
count of how many are positive, i.e., greater than zero.
- Use the stepper on
count-positive applied to
a list of length 2.
How many times is your function called
(counting both the initial call and recursive calls)?
- Develop a program
map-add
which takes a list of numbers and another number
and returns a list of numbers, where the original list's
elements have been added to the other number. E.g.,
(map-add (cons 1 (cons 3 (cons 4 empty))) 2)
results in
(cons 3 (cons 5 (cons 6 empty)))
Later in the course, we'll generalize this idea of
mapping some operation over a list to generate a new
list of the results.
- Develop a program
filter-positive
which takes a list of numbers and returns a list
of all those numbers which are positive. E.g.,
(filter-positive (cons 1 (cons -5 (cons 3 empty))))
results in
(cons 1 (cons 3 empty))
Later in the course, we'll generalize this idea of
filtering a list by some test condition.
|
We've seen lists of symbols and lists of numbers; you can of course have a list
with elements of any given type …
including other structures like posns.
This just uses ideas you've already learned, but in new contexts.
Exercises
- Define the type of lists of
posns.
- Write the templates of lists of
posns.
(There are two non-primitive types here,
so you need two templates!)
- Write the function
positive-quadrant?,
which takes in a single posn and
returns true exactly when its components are both positive.
- Develop count-positive-quadrant,
which takes a list of
posns and
returns a count of those in the upper-right quadrant.
- Develop filter-positive-quadrant,
which takes a list of
posns
and returns a list of those in the upper-right quadrant.
|
Optional: Non-empty lists
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 list 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 standard, potentially
empty 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 one of them.
|