|
Comp210: Principles of Computing and Programming
Fall 2004 -- 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:
Review: A new flavor of define
,
Review: Design Recipe Review,
Lots of Examples
Quick Review: A new flavor of define
Labby note: Just skim this section.
We saw in class a new way to use define
. Our original usage, if you
think about it, really does
two separate things. First, a new function is created (here, it takes
in a number and returns a number); Second, a name is associated with that
function ("circle-area
").
;; circle-area: number -> number
(define (circle-area r)
(* pi (* r r)))
The new way to use define
actually is simpler: it simply associates
a name with a value (not (necessarily) a function). Some people call these names
variables, though they never actually vary. We'll call them
placeholders.
(define speed-limit 55)
(define international-greeting 'hello)
(define my-favorite-number (+ 15 2))
(define my-favorite-ppg (make-ppg 'Buttercup 'green 90 ))
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 ppg
s,
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.
For discussion
- How do these principles apply to a program using "55" vs. a program
mentioning
speed-limit ?
- 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?
For constants like
0 , 1 ,
true , false , and empty , it generally
doesn't make sense 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.
|
Summary of define
syntax
-
(define (placeholder parameters...)
body-expression)
The placeholder is the function name. The body-expression can be any
expression, presumably involving the parameter.
-
(define placeholder expression)
define
question
How does the computer tell these two cases apart?
Hint:
Pay attention to which parentheses belong to the define , and
which are actually part of various sub-expressions.
|
Review: List Definition and Revised Design Recipe
Definition review question
Answer/discuss the following as a group.
- What is the data definition of a list of symbols?
- What are the constructors, selectors, and predicates for lists of
symbols?
- What is the template for functions on lists of symbols?
|
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.
Steps depending only on the data:
- Data analysis:
How, exactly, do you represent the problem in terms of Scheme data?
Create a data definition and matching function template.
- Case analysis:
Does your data has several possible forms? In the template, create
a
cond
with one branch per case of data. (You can add
one more case for error-checking.) Write all the cond
's
questions, to distinguish between the cases. (We will fill in the
particular answers only when we have a particular function.)
- Structure analysis:
Within each case, should this data be a structure? Of what? Your
template should illustrate the possible selectors, like a good
craftsperson or artisan inspecting what tools are available to
complete the task with, before launching in blindly.
- new
Natural recursion:
For each of the pieces from the previous step, ask yourself what
type of data it is, and call an appropriate function. If the
sub-datum's type is the same as the input of the entire function,
this suggests a recursive function.
- Data examples.
Steps depending on the function:
- Function contract, purpose, header.
- Function test cases:
Use your previously-written data examples.
- Function body:
Copy the template. Since there is one template per data-definition, you
often have many functions based on the same template.
- Function testing:
Use 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
Labby note: Pick some to work as a group, and leave time for
them to work on others independently.
There are many more examples here than you can do in lab. Students should look
over the rest on their own. We strongly encourage you to use
DrScheme's stepper on at least some of these examples.
Lists of numbers
Series of list of numbers exercises
- Make the data definition and template for list-of-numbers.
(Extremely similar to list-of-symbols.)
- Make some examples of lists of numbers.
- 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)) ? We'll stop reminding you now.)
- 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. In particular, what number
makes sense as the sum of no numbers?
- Develop a program which takes a list of numbers and returns the
product of all the numbers. In particular, what number makes
sense as the product of no numbers?
- Develop a program 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.,
(add-numbers (cons 1 (cons 3 (cons 4 empty))) 2)
=
(cons 3 (cons 5 (cons 6 empty)))
- Develop a program which takes a list of numbers and returns a list
of all those numbers which are positive.
|
Databases
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.
- 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!
|
For the curious... Non-empty lists
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 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.
|
Note: There are actually
two reasonable solutions to this, although we
hinted towards one of them.
|
Last Revised
Tuesday, 24-Aug-2004 13:49:16 CDT
©2004 Stephen Wong and Dung Nguyen