Class 27: Association Lists

Back to Pairs. On to Vectors.

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:

Assignments

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

History

Thursday, 16 January 2003 [Samuel A. Rebelsky]

• First version, created mostly automatically from previous course.

Tuesday, 4 March 2003 [Samuel A. Rebelsky]

• Filled in introductory material.

Back to Pairs. On to Vectors.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 6 09:29:58 2003.
The source to the document was last modified on Tue Mar 4 21:20:37 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Outlines/outline.27.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu