[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
In today's laboratory, you will experiment with association lists, structures that make it easy to look up information.
You may want to scan through the reading
on association lists. Make sure that you know what the
assoc
procedure does. You may also want to remind yourself
of the topics in the reading on
pairs.
Define an association list birth-dates
that associates the
surnames of recent presidents of the United States (as strings) with their
birth-dates (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:
President | Date of birth |
---|---|
Clinton | August 19, 1946 |
Bush | June 12, 1924 |
Reagan | February 6, 1911 |
Carter | October 1, 1924 |
Ford | July 14, 1913 |
Nixon | January 9, 1913 |
Johnson | August 27, 1908 |
Kennedy | May 29, 1917 |
Eisenhower | October 14, 1890 |
Use the assoc
procedure to search the birth-dates
association list for someone who is on the list and for someone who is not
on the list.
a. Redefine birth-dates
so that it includes two entries with the
same key, for two people who have the same surname -- say, John Adams (born
October 30, 1735) and John Quincy Adams (born July 11, 1767). What happens
if you try to apply assoc
to retrieve these entries, using the
common key "Adams"
?
b. Many people find these results disappointing. To help alleviate this
disappointment, define and test a procedure 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's given
a list which contains a non-pair as an argument?
b. What do you think assoc
will do if one of the elements
in the association list is a list, rather than a pair. For example,
what should happen with
> (assoc 'a (list (cons 'b 'beta) (list 'a 'alpha))
c. Confirm or refute your answers by experimentation.
d. Based on your experience, what preconditions should
assoc
have?
a. What happens if you search by date instead of by person? (For example, you
might try (assoc "October 1, 1924" birth-dates)
.)
b. Define and test a procedure
reverse-lookup
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 a pair exists
#f
if there is no such pair.
c. Define and test a procedure that takes
an association list
alist
and an associated datum val
, and returns
a list of all pairs that have val
as the second component.
a. Define and test a procedure that takes two arguments, the first a positive
integer sought
and the second an association list
als
in which all of the keys are natural numbers, and returns
the first pair in als
in which the car is evenly divisible by
sought
.
(In other words, this procedure works like assoc
, except that
you can recover a pair from the association list if you know any divisor of
its key, without having to know the key itself.)
b. Why might you want to use this procedure?
c. Define and test a procedure 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.
d. Why might you want to use this procedure?
Note: The value of birth-dates
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 birth-dates
should take.
Tuesday, 19 September 2000
http://www.math.grin.edu/~stone/courses/scheme/association-lists.xhtml
[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/alist.html
Source text last modified Wed Sep 20 14:00:15 2000.
This page generated on Wed Sep 20 14:01:26 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu