a. Make a copy of association-lists-lab.rkt.
b. Review the definitions in that code to make sure you understand what procedures and values are being defined.
a. As you’ll note from the provided code, we use “directory” to refer to
an association list in which each entry is a list of the form
'(last first username phone attribute-1 ... attribute-n).
Write 6P-style documentation for a procedure,
last-name directory), that lets you find the attributes
associated with a particular last name. The procedure should return
#f if there is no element with tha tlast name.
> (lookup-attributes "Weinman" grinnell-directory-annotated) '("CSC" "Chair" "Associate" "NSF Grant") > (lookup-attributes "Smith" grinnell-directory-annotated) #f > (lookup-attributes "Kington" grinnell-directory-annotated) '("Bigwig")
You may wish to consult the documentation for
lookup-email-by-last-name to guide you.
b. Write the procedure
assoc to do the
Note: Since you are using
assoc to do the searching, your goal is
primarily to extract the attributes once you’ve found the appropriate
Hint: The goal of this procedure is similar to the goal of
lookup-email-by-last-name. You may consider using the definition
of that procedure as a model for designing this procedure. If you do,
remember to give an appropriate citation.
a. Define an association list,
sidekicks, that associates the names of
some famous cartoon protagonists (as strings) with the names of their
sidekicks (again, as strings).
You may also want to look at the note on this exercise.
Here’s a table containing information for your association list:
|Secret Squirrel||Morocco Mole|
|Quick Draw McGraw||Baba Looey|
|Bart Simpson||Milhouse Van Houten|
|Strong Bad||The Cheat|
b. Use the
assoc procedure to search the
sidekicks association list
for someone who is on the list and for someone who is not on the list.
sidekicks so that it includes two entries with the same
protagonist and different sidekicks – say Scooby Doo, who has both
Shaggy and Scrappy Doo as sidekicks. What do you expect to happen if
you try to apply
assoc to retrieve these entries, using the common key
b. Check your answer experimentally.
c. Many people find these results disappointing. To help alleviate this
disappointment, define and test a recursive procedure,
alist), similar to
assoc, except that it returns a list of all
the lists with the given key.
a. What happens if you search the hero/sidekick list by sidekick instead of by protagonist? For example, you might try
> (assoc "Chumley" sidekicks)
b. Define and test a recursive procedure
(assoc2 val alist)
valas its second component, if such an element exists;
#fif there is no such element.
c. Define and test a recursive procedure that takes two parameters, an
alist, and an associated datum,
val, and returns
a list of all elements that have
val as the second component. You may
assume that all elements of
alist are lists of at least two elements.
Suppose we add the following entries to the end of the College directory.
(list "Moore" "Emily" "emoore" "4205" "MAT" "Emeritus" "CSC") (list "Moore" "Tom" "tmoore" "0000" "Statistics" "Emeritus" "MAT") (list "Moore" "Orless" "punny" "1234" "CSC" "Emeritus" "Fictitious" "NSF Grant")
As you’ve found, when there are multiple elements with the same key,
assoc returns the first. For situations like that, we might want
to have a compound key, consisting of the first and last name.
Write a procedure
(lookup-phone-by-name name directory)
that looks someone up by the full name in the directory.
> (lookup-phone-by-name "Tom Moore" grinnell-directory-annotated) "0000" > (lookup-phone-by-name "emily moore" grinnell-directory-annotated) "4205" > (lookup-phone-by-name "Ed Moore" grinnell-directory-annotated) #f
So far, we haven’t used the last part of each entry, the attributes that someone has assigned to the person in the directory. Note that we can get those attributes by dropping the first four elements of the entry.
a. Write a recursive procedure,
dictionary), that returns a list of the last names in the
entries that contain the given attribute. For example,
> (lookup-names-by-attribute "Assistant" grinnell-directory-annotated) '("Klinge" "Osera" "Curtsinger" "Vostinar" "Rodrigues") > (lookup-names-by-attribute "DigHum" grinnell-directory-annotated) '("Rebelsky" "Rodrigues") > (lookup-names-by-attribute "Annoying" grinnell-directory-annotated) '() > (lookup-names-by-attribute "PM" grinnell-directory-annotated) '()
You may find the following procedure useful.
;;; Procedure: ;;; list-contains? ;;; Parameters: ;;; lst, a list ;;; val, a value ;;; Purpose: ;;; Determines if lst contains val. ;;; Produces: ;;; contained?, a Boolean ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; If there is an i such that (list-ref lst i) equals val, ;;; then contained? is true (#t). ;;; Otherwise, ;;; contained? is false. (define list-contains? (lambda (lst val) (and (not (null? lst)) (or (equal? (car lst) val) (list-contains? (cdr lst) val)))))
b. Suppose we wanted to find names that are both in CSC and Assistant Professors. Describe a process for doing so. Don’t write a new procedure; preferably, you should do this with a few commands in the interactions pane.
assoc, we can only search the directory by complete last
name. Write a procedure
(lookup-by-prefix prefix directory)
that searches directory for the first entry in which prefix is a prefix
of the last name.
> (lookup-by-prefix "Rebel" grinnell-directory-annotated) '("Rebelsky" "Samuel" "messy-office" "4410" "CSC" "151prof" "DigHum" "Professor") > (lookup-by-prefix "King" grinnell-directory-annotated) '("Kington" "Raynard" "the-prez" "3000" "Bigwig") > (lookup-by-prefix "K" grinnell-directory-annotated) '("Klinge" "Titus" "cauldron" "3271" "CSC" "Assistant" "151prof") > (lookup-by-prefix "Octothorpe" grinnell-directory-annotated) #f
Here you will find notes on selected problems.
Note: The value of
sidekicks is not a procedure, so it is not necessary
to use a
lambda-expression in this exercise. Look at the definition of
grinnell-directory for an example of the form that your definition of
sidekicks should take.
If we remember correctly, the table of cartoon characters and some of the related problems are due to Ben Gum.