Fundamentals of Computer Science 1 (CS151 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
Summary: In today's laboratory, you will experiment with association lists, structures that make it easy to look up information.
Contents:
Useful procedures:
assoc
,
list-ref
,
member
.
a. Make sure you know what the assoc
procedure does.
b. Start DrScheme
In the reading on association lists,
we claimed that the look-up-telephone-number
procedure worked
correctly, even for the extended table that included not only phone
number, but also department.
Verify that claim.
You can find the table and the code at the end of this lab.
Write and document a procedure, (look-up-division name
directory)
, that someone can use to look up the
department associated with a chair.
Define an association list, sidekicks
, that associates the
names of some famous cartoon protagonists (as strings) with the names
of their sidekicks (again, as strings).
You may also want to look at the note on this exercise.
Here's a table containing information for your association list:
Protagonist | Sidekick |
---|---|
Peabody | Sherman |
Yogi | Booboo |
Secret Squirrel | Morocco Mole |
Tennessee Tuxedo | Chumley |
Quick Draw McGraw | Baba Looey |
Dick Dastardly | Muttley |
Bullwinkle | Rocky |
Bart Simpson | Milhouse Van Houten |
Asterix | Obelix |
Use the assoc
procedure to search the sidekicks
association list for someone who is on the list and for someone who is not
on the list.
a. Redefine sidekicks
so that it includes two entries with the
same protagonist and different sidekicks -- say Scooby Doo, who has both
Shaggy and Scrappy Doo as sidekicks.
What happens
if you try to apply assoc
to retrieve these entries, using the
common key "Scooby Doo"
?
b. Many people find these results disappointing. To help alleviate this
disappointment, define and test a procedure,
(multi-assoc key alist)
,
similar to assoc
,
except that it returns a list of all the pairs with the
given key.
a. What do you think that assoc
will do if it is given
a list in which each element is a pair, rather than a list? For
example, can we use assoc
to search the following list
to determine the last name of a faculty member?
(("Sam" . "Rebelsky") ("Henry" . "Walker") ("John" . "Stone") ("Ben" . "Gum") ("Emily" . "Moore") ("Tom" . "Moore") ("Pam" . "Ferguson") ("Gene" . "Herman") ("Chris" . "Hill") ("Marc" "Chamberland") ("Royce" . "Wolf") ("Chuck" . "Jepsen") ("Arnie" . "Adelberg"))
b. Confirm or refute your answers by experimentation. If you're not sure how to create that list, check the notes on this problem, which give instructions for creating that list.
c. Based on your experience, what preconditions should
assoc
have? (No, you may not read the online
documentation for an answer.)
a. What happens if you search by sidekick instead of by protagonist? For example, you might try
(assoc "Chumley" sidekicks)
b. Define and test a procedure
lookup-by-second
that takes two arguments,
an association list
alist
and an associated datum val
, and returns
alist
that has val
as its second
component, if such an element exists
#f
if there is no such element.
c. Define and test a procedure that takes two parameters, an association
list, alist
, and an associated datum, val
, and
returns a list of all elements that have val
as the second
component.
For some problems, it seems natural to always use a specific database, rather than to pass the database as a parameter. For example, suppose we'd set up a table of science department chairs (which may sound familliar from the reading, although we've expressed it differently here).
;;; Value: ;;; science-department-chairs ;;; Type: ;;; List of lists. ;;; Each sublist is of length two and contains a department (or "science") ;;; and a name. ;;; Both of those values are strings. ;;; Contents: ;;; A list of the department and division chairs in the Science division ;;; in academic year 2000-2001. (define science-department-chairs (list (list "Science" "Mark Schneider") (list "Biochemistry" "Bruce Voyles") ; Well ... (list "Biology" "Jackie Brown") (list "Chemistry" "Martin Minelli") (list "Math/CS" "Gene Herman") (list "Mathematics" "Gene Herman") ; For those who forget CS (list "Computer Science" "Gene Herman") ; For other folks (list "Physics" "Charles Cunningham") (list "Psychology" "Ann Ellis")))
We can write a procedure to look up a department chair as follows:
;;; Procedure: ;;; look-up-science-chair ;;; Parameters: ;;; dept, the name of a science deparment (or simply "Science") ;;; Purpose: ;;; Look up the chair of a science department. ;;; Produces: ;;; chair, a string (or #f) ;;; Preconditions: ;;; science-department-chairs must be defined appropriately ;;; dept must be a string ;;; Postconditions: ;;; If science-department-chairs specifies a chair for dept, ;;; chair is that chair. ;;; Otherwise, chair is false (#f) (define look-up-science-chair (let ((lusc-helper (lambda (assoc-result) (if assoc-result (cadr assoc-result) #f)))) (lambda (dept) (lusc-helper (assoc dept science-department-chairs)))))
The strategy of using a specific database in a procedure is often called hard-coding the database.
a. Using look-up-science-chair
, look up the chair of
this department.
b. Using look-up-science-chair
, look up the chair of Geology.
c. Suppose we wanted to write the converse procedure (one that given a name, tells which department he or she chairs). Can we still hard-code the database? If so, show how. If not, explain why not.
a. Define and test a procedure, (weird-lookup sym
weirdlists)
, that takes two arguments, the first an atom and
the second an association list whose keys are all lists of atoms.
The procedure should return a list of all the values whose keys contain
the atom. For example,
> (define whatever (list (list (list 'a 'b 'c) 'ABCs) (list (list 'a 'e 'i 'o 'u) 'vowels) (list (list 'e 't 'a 'i 'o 'n) 'shrdlu))) > (weird-lookup 'a whatever) (abcs vowels shrdlu) > (weird-lookup 'b whatever) (abcs) > (weird-lookup 'o whatever) (vowels shrdlu) > (weird-lookup 'q whatever) ()
Note that you might find the member
procedure helpful.
b. Why might you want to use this procedure?
Consider the following list of faculty in Mathematics and Computer Science.
(define mathcs (list (cons "Sam" "Rebelsky" "Associate" "Computer Science") (cons "Henry" "Walker" "Chaired" "Computer Science") (cons "John" "Stone" "Instructor" "Computer Science") (cons "Ben" "Gum" "Assistant" "Computer Science") (cons "David" "Bishop" "Visitor" "Computer Science") (cons "Emily" "Moore" "Full" "Mathematics") (cons "Tom" "Moore" "Full" "Statistics") (cons "Pam" "Ferguson" "Chaired" "Mathematics") (cons "Gene" "Herman" "Chaired" "Mathematics") (cons "Chris" "Hill" "Visitor" "Mathematics") (cons "Marc" "Chamberland" "Assistant" "Mathematics") (cons "Royce" "Wolf" "Chair Apparent" "Mathematics") (cons "Chuck" "Jepsen" "Full" "Mathematics") (cons "Arnie" "Adelberg" "Chaired" "Mathematics")))
When looking up people, we might want to make sure that we match
both first and last names. Write a procedure,
(lookup first last people)
that
extracts the entry in which both first and last
match.
Here you will find notes on selected problems.
Here's the revised table, just in case you've forgotten.
(define science-chairs-directory (list (list "Mark Schneider" "3018" "Science") (list "Jackie Brown" "3096" "Biology") (list "Martin Minelli" "3007" "Chemistry") (list "Gene Herman" "4202" "Math/CS") (list "Charles Cunningham" "3182" "Physics") (list "Ann Ellis" "4865" "Psychology")))
And here's the code for look-up-telephone-number
.
;;; Procedure: ;;; look-up-telephone-number ;;; Parameters: ;;; name, a string ;;; directory, a list of telephone book entries ;;; Purpose: ;;; Looks up someone's telephone number in the directory. ;;; Produces: ;;; number, a string ;;; Preconditions: ;;; Each telephone book entry must be a list. [Unverified] ;;; Element 0 of each telephone book entry must be a string which ;;; represents a name. [Unverified] ;;; Element 1 of each telephone book entry must be a string which ;;; represents that person's phone number. [Unverified] ;;; Postconditions: ;;; If an entry for name appears somewhere in the directory, returns ;;; the corresponding phone number. ;;; If multiple entries with the same name appear, returns one of them. ;;; If no entries appear, returns the string "unlisted" ;;; Does not affect the directory. (define look-up-telephone-number (let ((lutn-helper (lambda (assoc-result) (if assoc-result (cadr assoc-result) "unlisted")))) (lambda (name directory) (lutn-helper (assoc name directory)))))
Note: The value of sidekicks
is not a procedure, so it is not
necessary to use a lambda
-expression in this exercise. Look
at the definition of science-chairs-directory
for an example
of the form that your definition of sidekicks
should take.
You can create that list with
(define mathcs (list (cons "Sam" "Rebelsky") (cons "Henry" "Walker") (cons "John" "Stone") (cons "Ben" "Gum") (cons "David" "Bishop") (cons "Emily" "Moore") (cons "Tom" "Moore") (cons "Pam" "Ferguson") (cons "Gene" "Herman") (cons "Chris" "Hill") (cons "Marc" "Chamberland") (cons "Royce" "Wolf") (cons "Chuck" "Jepsen") (cons "Arnie" "Adelberg")))
Tuesday, 19 September 2000 [Samuel A. Rebelsky]
http://www.math.grin.edu/~stone/courses/scheme/association-lists.xhtml
Wednesday, 20 September 2000 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/alists.html
.
Wednesday, 21 February 2001 [Samuel A. Rebelsky]
Thursday, 22 February 2001 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/alists.html
.
Sunday, 29 September 2002 [Samuel A. Rebelsky]
Wednesday, 2 October 2002 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/alists.html
.
Tuesday, 4 March 2003 [Samuel A. Rebelsky]
For those with extra time.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Labs/alists.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue May 6 09:28:36 2003.
The source to the document was last modified on Tue Mar 4 22:17:58 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Labs/alists.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby