Held Wednesday, September 20, 2000
Today we visit a database-like application of Scheme: Association lists.
Association lists allow you to associate information with a ``key''
and then look up the value by the key.
- Lab: Association lists
- Reading for Friday: Vectors
- The reading won't be ready until this afternoon.
- A reminder: There is almost always a link to the current lab at the
top of the current day's outline.
- Another reminder: You can certaionly come to see me when you need help
- I haven't had many visitors, so I'm not sure if you're all getting
the material well or ...
- I'll be in the office until about 2:45 today (I'm picking up my
son after school) and most of the day tomorrow.
- As I hinted at in
the reading on association lists,
there will be a quiz today.
- Association lists
- Sequential search
- Databases are among the most common applications of computers.
- After all, there's a reason that Larry Ellison is nearly as rich
as Bill Gates.
- At the simplest level, a database is a mechanism for storing data
so that you can easily access the data you need.
- Simple databases in which you can associate a value (or values) with
a particular key are called dictionaries.
- In Scheme, dictionaries are typically implemented with a data structure
known as the association list.
- An association list is simply a list of
- You can use the
(assoc key list)
procedure to look up values by key.
- Suppose Scheme didn't include
assoc. How would you write
- If the list is empty, it does not contain the value.
- If the key of the first pair in the list is the key, return the
- Otherwise, look in the rest of the list.
- This technique is called sequential search.
- We'll turn that into Scheme together.