Outline 44: Association Lists

Held: Monday, 20 April 2015

Summary

We consider association lists, a simple, but useful, technique for organizing tables of information.

Related Pages

Overview

Administrivia

New partners!
Welcome prospectives!
Review session tonight at 8pm.
Lots of office hours this week.
- Check http://rebelsky.youcanbook.me
- 3:15-4:00 is available today, but not appearing. Email me to reserve today's afternoon times.
Tomorrow is planned as a pseudo-Socratic session. Please make sure to do the reading.
YY is a social issue, not a technological one. It needs social solutions. I reiterate: Please work with your peers to improve how we treat each other.

KY's radio show, "We Think We're Funny", 9-10pm Mondays.
Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.

Notes distributed via email at the start of class.
I am sorry that I had to send mail about another academic honesty issue. My goal (and I think the College's) is primarily education, not punishment.
To invoke "There's More to Life",
- You need to meet with me within the next week.
- You need to have read the notes on the exam (at least the introductory notes and the sample solutions) before meeting with me.
- You need to bring your exam to the meeting with me.
- You should have recorded your times.

I've added a variety of project tips that I thought we'd look at quickly. More to come.

Simple Database Problems

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.
A database is a mechanism for storing data so that you can easily access the data you need.
One simple database activity is looking up values by keys.
Databases that provide only that activity are called dictionaries.

In Scheme, dictionaries are typically implemented with a data structure known as the association list.
An association list is a list of elements each of which has a key as its car.
You can use the (assoc *key* *list*) procedure to look up values by key.

Suppose Scheme didn't include assoc. How would you write it? Probably recursively.
If the list is empty, it does not contain the value.
If the key of the first element in the list is the key we're looking for, return the corresponding value.
Otherwise, look in the rest of the list.
This technique is called sequential search.

Given that we can write our own assoc procedure, we can easily implement a number of interesting variants of association lists.
For example, if the same key appears multiple times in the association list, we might return all matching values (rather than the first matching value).
Similarly, instead of searching by key, we might search by predicate.