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:
A new flavor of define
,
Definition and Design Recipe Review,
Lots of Examples
A new flavor of define
We saw today in lecture, a new way to use define
.
Our original usage, if you think about it, really does
two separate things:
;; circle-area: number -> number
(define (circle-area r)
(* pi (* r r)))
First, a new function is created (it takes in a number
and returns a number);
Second, a name is associated with that function ("circle-area
").
The new way to use define
actually is simpler:
it simply associates a name with a value (not (necessarily) a function).
(define speed-limit 55)
(define international-greeting 'hello)
(define my-favorite-number (+ 15 2))
(define my-favorite-ppg (make-ppg 'buttercup 'green 90 ))
Some people call these names "variables",
though they never actually vary.
We'll call them "placeholders".
All placeholders do is save us typing.
Whereever in a program you see speed-limit
,
you could conceivably re-write the program to use 55
,
and the program's behavior will be the same.
Thus it's a handy way to save typing of structures (like PPGs,
which are tedious to type).
Nothing else mysterious happens.
Note that use of placeholders is important in both
-
having your program reflect how you think of the problem, and
-
single point of control.
Discuss: how do these principles apply to
a program using "55" vs a program mentioning "speed-limit".
What if you use a such a number only once? --
should you use the number directly, or define a placeholder for it?
(Do the two principles still apply?)
Exception: for constants like
0, 1, true, false,
and
empty
you don't need to define separate placeholders.
These two uses of define
are certainly related --
the function version does extra work of creating a function,
but after that they are identical:
If you think of functions as just being another type of value
(in addition to numbers, symbols, booleans, and structures),
then
in either case,
a placeholder is being associated ("bound") to a value.
Note for the curious: we'll see later how to create a function
without needing to give it a name.
Syntax for define
(summary)
How does the computer tell these two cases apart?
Pay attention to which parentheses belong to the define
,
and which are actually part of various sub-expressions.
Definition and Design Recipe Review
We'll go over the
lecture notes,
actually typing in the examples presented there.
The goal is to be comfortable with:
-
Understanding the data definition for a list-of-symbols
(constructors, selectors, predicates).
-
Typing in examples of a list-of-symbols,
and extracting pieces therefrom.
-
Writing a function processing a list-of-symbols (of any length!)
(using examples from more lecture notes)
-
Understanding the
revised Design Recipe, having now added
recursive data definitions.
-
Using the stepper to come to grips (intellectually and emotionally)
with recursion.
-
Practice.
Now, let's quickly review our latest design recipe.
We know our programs should take advantage of the structure of the data;
recursive data implies recursive functions.
- 1. data definition
How, exactly, do you represent the problem in terms of Scheme data?
- 2. Example data.
You'll also use these data for testing specific functions later,
but this is an important step in its own right.
- 3. Template
The part of the function which reflects the structure of the data.
- case analysis:
If your data has various cases,
include a cond
-- one branch per case of data.
(Note: Write all the cond
questions first,
to distinguish the data;
not 'til we have a particular function
will we fill in the particular answers (step 6).)
- Data extraction
If your data is a structure, your code will be using the
various selectors for that structure,
like a good craftsperson or artisan inspecting what tools are available to
complete the task with, before launching in blindly.
- Add natural recursion
For each of the pieces from the previous step, ask yourself
what type of data it is, and call an appropriate funciton.
If the sub-datum's type is the same as the input of the entire
function, this suggests a recursive function.
(N.B. You write this generic template before you want to write any
particular function on the data.)
- 4. Contract, purpose, header for the function.
- 5. Develop test cases for the function.
- 6. Write the body of the function.
(You'll start by copy/pasting your template.
Note that there is one template per data-definition;
you will often have many functions based on the same template.)
- 7. test your function (using your previously-written test cases)
An English aside:
"To recur" is what programs do;
"to recurse" is what you may sometimes do in frustration.
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.
|
Note to labbies: We'll get aobut this far.
Students who want to work ahead in labs can try the following
examples.
Databases (Optional)
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 villains.
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:
(define-struct villain (name power always-hungry? iq weakness))
;;
;; A villain is:
;; (make-villain [symbol] [number] [boolean] [number] [symbol])
;; where power is the power-rating, iq is an IQ.
;; weakness describes the villain's achilles heel.
;; name and always-hungry? are self-evident.
; Examples of data:
(make-villain 'fuzzy-lumpkins 90 true 35 'witty-banter)
(make-villain 'mojo-jojo 35 false 190 'soliliquizing)
#|
;;;; TEMPLATE
;; villain-handler: villain --> ??
;;
(define (villain-handler a-villain)
..(villain-name a-villain) ..(villain-power a-villain)
..(villain-iq a-villain) ..(villain-always-hungry? a-villain)
..(villain-weakness a-villain) )
|#
- Create some more example villains.
- Create a template for villains (simple).
- Write the function dangerous?, which
takes in a single villain, and returns true exactly when
the villain has an iq over 190, or a toughness over 50.
(Hint: the english description uses "or"; your code may use
or !)
- The mayor wants you to keep a crime-database.
Hmm, what data type is appropriate, to represent a crime-database?
- Write the template for functions which handle entire crime-databases.
- Develop number-dangerous, which takes a crime-database and
returns
a count of those
villains who
have an iq over 190 or a toughness over 50.
(Hint: Remember the principle of not repeating code!)
- For the curious...
Develop dangerous-names, which takes a database and returns
a list of those employees' names.
Follow the template!
|