Fundamentals of Computer Science I (CSC-151.02 2000F)

Association Lists

In today's laboratory, you will experiment with association lists, structures that make it easy to look up information.


Exercise 0: Preparation

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.

Exercise 1: Birthdays

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

Exercise 2: Finding Birthdays

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.

Exercise 3: Duplicate Keys

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.

Exercise 4: Preconditions

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?

Exercise 5: Reverse Associations

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

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.

Exercise 6: Compound Keys

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 on exercise 1

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

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

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