Class 27: Association Lists

Held: Wednesday, 5 March 2003

Summary: 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.

Related Pages:

• EBoard.
• Reading on Association Lists.
• Lab on Association Lists.

Assignments

• Read Vectors.

Notes:

• I still need your lists of books. You can see the current list of books at http://www.cs.grinnell.edu/~rebelsky/Scheme/books.html. Please use the format

  (list "author-last" "author-first" "title"
        (list "adj1" "adj2" "adj3" "adj4" "adj5"))
  

• Are there questions on homework 3?
• I will not be here for Friday's class. If you have questions, please email them before Friday (or you won't get an answer until late Sunday night).
• My wife has asked me to help find a volunteer student tutor for a seven-year-old. Anyone know who might be willing to help?
• I assume most of you are stressed enough with pre-break stuff, so I won't assign any more homework, exams, or lab writeups before break. I'd like you to use some of the saved time on labs.
• There was some confusion on the listp? procedure, so we'll go over some variations.

Overview:

• Databases and dictionaries.
• Lists as dictionaries.
• assoc, a procedure for searching lists.
• Lab.

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.
• At the simplest level, a database is a mechanism for storing data so that you can easily access the data you need.
• Simple databases (or tables within databases) in which you can associate a value (or values) with a particular key are called dictionaries.

Association Lists

• In Scheme, dictionaries are typically implemented with a data structure known as the association list.
• An association list is simply 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.

Searching in Association Lists

• 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.

Lab

• Do the lab.
• You won't finish today. Try to work on it tonight and tomorrow. Come with questions on Monday.