Fundamentals of Computer Science I (CS151 2003F)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Guidelines for Lab Writeups]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Scheme Report]
[Glimmer Scheme Reference]
[CSC151.01 (Gum)]
[CSC151 2003S]
[CSC151 2002F]
[SamR]
Summary: We consider a number of Scheme procedures that can be used to look up information.
Contents:
assoc
, Scheme's Built-in Lookup Procedure
assoc
Procedures covered in this reading:
Consider the organization of a simple telephone directory for on-campus
telephones: a sequence of entries, each consisting of a name and a
four-digit telephone number. In Scheme, it is natural to use strings for
names; it turns out that telephone numbers should also be represented as
strings, since string operations make a useful kind of sense when applied
to telephone numbers and integer operations do not. (For instance,
(string-append "269-" extension)
does something
useful if the value of extension
is a string, but not if
it is an integer.)
To represent each individual entry in a telephone directory, we can use
a list, such as ("Henry Walker" "4208")
,
("John Stone" "3181")
, or
("Sam Rebelsky" "4410")
, with the name as
the car of the entry and a list of the telephone number as the
cadr. An entire directory, then, would be a list of such entries:
;;; Value: ;;; science-chairs-directory ;;; Type: ;;; List of lists. ;;; Each sublist is of length two and contains a name and a phone number. ;;; Both of those values are strings. ;;; Contents: ;;; A list of the department and division chairs in the Science division ;;; in academic year 2002-2003. (define science-chairs-directory (list (list "Mark Schneider" "3018") (list "Jackie Brown" "3096") (list "Martin Minelli" "3007") (list "Gene Herman" "4202") (list "Charles Cunningham" "3182") (list "Ann Ellis" "4865")))
In Scheme, a list of pairs or lists is called an association list or alist.
As the telephone-directory example illustrates, a particularly common
application of association lists involves looking for a desired name or
first component of a pair and retrieving the second component of a pair.
Thus, the first component of each pair (the car
of a pair)
often is called a key, and the cdr
of the pair is
its associated data or value. For example, in the above
illustration, "Martin Minelli"
,
"Gene Herman"
, and "Ann Ellis"
are some of the keys, and the lists that contain only telephone numbers
are the associated data. Thus an association list is a simple way to
implement a small table in a database.
assoc
, Scheme's Built-in Lookup Procedure
Since such applications are very common, Scheme provides procedures to
retrieve from an association list the pair containing a specified key. The
most frequently used procedure of this kind is assoc
. Given a
key and association list, assoc
returns the first pair with
the given key. If the key does not occur in the association list, then
assoc
returns #f
. For example,
> (assoc "Gene Herman" science-chairs-directory) ("Gene Herman" "4202") > (assoc "Sam Rebelsky" science-chairs-directory) #f
To find the telephone number corresponding to a given name, we could
apply the cadr
(car of cdr)
procedure to the result of assoc
. Here's an example.
;;; Procedure: ;;; look-up-telephone-number ;;; Parameters: ;;; name, a string ;;; directory, a list of telephone book entries ;;; Purpose: ;;; Looks up someone's telephone number in the directory. ;;; Produces: ;;; number, a string ;;; Preconditions: ;;; Each telephone book entry must be a list. [Unverified] ;;; Element 0 of each telephone book entry must be a string which ;;; represents a name. [Unverified] ;;; Element 1 of each telephone book entry must be a string which ;;; represents that person's phone number. [Unverified] ;;; Postconditions: ;;; If an entry for name appears somewhere in the directory, returns ;;; the corresponding phone number. ;;; If multiple entries with the same name appear, returns one of them. ;;; If no entries appear, returns the string "unlisted" ;;; Does not affect the directory. (define look-up-telephone-number (lambda (name directory) (if (assoc name directory) (cadr (assoc name directory)) "unlisted")))
For example,
> (look-up-telephone-number "Gene Herman" science-chairs-directory) "4202" > (look-up-telephone-number "Sam Smith" science-chairs-directory) "unlisted"
Note that the result depends on the directory. For example,
> (look-up-telephone-number "Gene Herman" null)
"unlisted"
Some of you may recall asking why if
might take a value other
than #t
or #f
as a parameter. This procedure
is one example of why.
One problem with the look-up-telephone-number
procedure
given above is that it calls assoc
twice, once to determine
whether the phone number is in the list and once to determine the
phone number. Rather than calling assoc
twice, we
might call it once and send the result to a helper procedure.
(define look-up-telephone-number (let ((lutn-helper (lambda (assoc-result) (if assoc-result (cadr assoc-result) "unlisted")))) (lambda (name directory) (lutn-helper (assoc name directory)))))
In the previous example, we have only one value (the phone number) associated with a key. However, in practice, we often want to associate many values with the same key. For example, we might want to note which department each chair is associated with. Here's a new version of our previous list that also includes that information.
;;; Value: ;;; science-chairs-directory ;;; Type: ;;; List of lists. ;;; Each sublist is of length three and contains a name, a phone number, ;;; and a division. ;;; All three of those values are strings. ;;; Contents: ;;; A list of department and other chairs in the Science division in ;;; academic year 2002-2003. (define science-chairs-directory (list (list "Mark Schneider" "3018" "Science") (list "Jackie Brown" "3096" "Biology") (list "Martin Minelli" "3007" "Chemistry") (list "Gene Herman" "4202" "Math/CS") (list "Charles Cunningham" "3182" "Physics") (list "Ann Ellis" "4865" "Psychology")))
You should note a few things about this list. First, we've left the
phone number as element 1 so that look-up-telephone-number
still works. Second, we've taken advantage of Scheme's decision to ignore
spaces between values by using spaces to put stuff in more tabular form.
assoc
As is the case with many of the built-in Scheme procedures,
assoc
is relatively easy to implement ourselves. In essence,
assoc
recursively steps through the list until it finds a
match or runs out of elements.
(define assoc (lambda (key alist) (cond ; If there are no entries left in the association list, ; there are no entries with the given key. ((null? alist) #f) ; If the key we're looking for is the key of the first ; entry, then use that entry. ((equal? key (car (car alist))) (car alist)) ; Otherwise, look in the rest of the association list. (else (assoc key (cdr alist))))))
The DrScheme implementation of assoc
also includes some
error checking that you'll learn how to do later this semester.
The assoc
procedure works fine if the key is the first element
of a data item. But what if it's the second (or third, or fourth, or ...).
For example, what if we know someone's phone number and want to find his
or her name? Then we can't rely on assoc
, because it only looks
at the first element of each list. Instead, we need to write our own
procedure. For example, to find someone with a particular phone number,
we might write:
;;; Procedure: ;;; look-up-by-number ;;; Parameters: ;;; number, a string ;;; directory, a list of telephone book entries ;;; Purpose: ;;; Looks up the entry for a particular phone number. ;;; Produces: ;;; entry, a telephone book entry. ;;; Preconditions: ;;; Each telephone book entry must be a list. [Unverified] ;;; Element 1 of each telephone book entry must be a string which ;;; represents that person's phone number. [Unverified] ;;; Postconditions: ;;; If an entry with phone number number appears in the directory, ;;; (1) number equals (list-ref entry 1); ;;; (2) entry is an element of directory ;;; If no entries with that phone number appear, entry is false (#f). ;;; Does not affect the directory. (define look-up-by-number (lambda (number directory) (cond ; If there are no entries in the directory, our desired ; entry is not there. ((null? directory) #f) ; If the number we're looking for is in the initial entry, ; use that entry ((equal? number (list-ref (car directory) 1)) (car directory)) ; Otherwise, look in the rest of the directory. (else (look-up-by-number number (cdr directory))))))
The assoc
procedure is actually one of three related built-in
procedures in Scheme; the other two are assq
and
assv
. Each of these procedures scan association lists for
keys. They differ only in the test used for determining when a key is found:
assoc
uses the predicate equal?
to compare
the key sought with the key components of the entries in the association
list.
assq
uses the predicate eq?
for those
comparisons.
assv
uses the predicate eqv?
for those
comparisons.
You may wish to refresh your memory on the purpose of these predicates (hint hint).
February 11, 2000 [Henry Walker and John Stone]
March 17, 2000 [John Stone]
http://www.cs.grinnell.edu/~stone/courses/scheme/spring-2000/association-lists.xhtml
Tuesday, 18 September 2000 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Readings/alists.html
.
Wednesday, 21 February 2001 [Samuel A. Rebelsky]
look-up-phone-number
to take a second
parameter.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Readings/alists.html
.
Sunday, 29 September 2002 [Samuel A. Rebelsky]
look-up-phone-number
.
assoc
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Readings/alists.html
.
Monday, 3 February 2003 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Readings/alists.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Guidelines for Lab Writeups]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Scheme Report]
[Glimmer Scheme Reference]
[CSC151.01 (Gum)]
[CSC151 2003S]
[CSC151 2002F]
[SamR]
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 Dec 9 14:00:06 2003.
The source to the document was last modified on Mon Sep 1 13:26:32 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003F/Readings/alists.html
.
; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu