Laboratory: Association Lists and Searching
Exercise 1: Color Tables, Revisited
In the reading on association
lists, we claimed that the lookup-color-by-name
procedure worked correctly, even for the extended table that included
not only color names and components, but also color attributes.
Verify that claim. That is, ensure that
lookup-color-by-name will find colors in the new table
and will return an appropriate error result for colors not in the table.
Exercise 2: Color Attributes
Document and write a procedure,
(lookup-attributes cname
ctable), that lets you find the attributes
associated with a particular color. (As a hint, use the built-in
assoc as a helper procedure.)
For example,
> (lookup-attributes "yellow" named-colors)
("rainbow" "secondary" "web-safe")
> (lookup-attributes "Oregon salmon" named-colors)
()
> (lookup-attributes "off white" named-colors)
("bw")
> (lookup-attributes "green" named-colors)
("primary" "web-safe")
Exercise 3: A Table of Named Shapes
Sometimes it is useful to think a drawing in terms of a collection
of named objects. Suppose we represent each object in the drawing
as a list of length 7: name, shape, color, left, top, width, height,
where the name, shape, and color are strings, the shape is either
"rectangle" or "ellipse", and the remaining
values are reals. For example,
(define drawing
(list (list "circ1" "ellipse" "red" 10 10 80 80)
(list "thin" "ellipse" "blue" 10 80 300 10)
(list "tall" "rectangle" "green" 80 5 100 2)
(list "ys1" "rectangle" "yellow" 0 50 10 10)
(list "ys2" "rectangle" "yellow" 0 50 20 20)
(list "ys3" "rectangle" "yellow" 0 55 30 30)
(list "ys4" "rectangle" "yellow" 0 60 40 40)
(list "ys5" "rectangle" "yellow" 0 65 50 50)
(list "ys6" "rectangle" "yellow" 0 70 60 60)
(list "rc" "ellipse" "red" 100 100 30 30)
(list "oc" "ellipse" "orange" 90 110 30 30)
(list "yc" "ellipse" "yellow" 80 120 30 30)
(list "gc" "ellipse" "green" 80 130 30 30)
(list "bc" "ellipse" "blue" 90 140 30 30)
(list "ic" "ellipse" "indigo" 100 150 30 30)
(list "vc" "ellipse" "violet" 110 160 30 30)
(list "last" "rectangle" "white" 0 0 1 1)))
Here is a procedure that you might find helpful as you
use these objects.
(define image.draw-named-object!
(lambda (image named-object)
(let ((type (list-ref named-object 1))
(color (list-ref named-object 2))
(left (list-ref named-object 3))
(top (list-ref named-object 4))
(width (list-ref named-object 5))
(height (list-ref named-object 6)))
(envt.set-fgcolor! color)
(if (equal? type "ellipse")
(image.select-ellipse! image selection.replace
left top width height)
(image.select-rectangle! image selection.replace
left top width height))
(image.fill! image)
(image.select-nothing! image))))
a. Copy the definitions of drawing and
image.draw-named-object! to the definitions pane.
Then, using image.draw-named-object! and
assoc, write an expression
that tells DrFu to draw the object from drawing
named "bc".
b. What do you expect to have happen if you use assoc
to find an object in drawing called
"thingy"? Check your answer experimentally.
c. The string "ellipse" appears a lot in
drawing. What do you expect to have happen if you
use assoc to find an object in
drawing called "ellipse"? Check
your answer experimentally.
Exercise 4: Finding Objects
a. Using assoc as a helper, write a procedure,
(find-object name
objects), that finds an object with the
given name in a list of shapes. If the object isn't found,
find-object should return false.
b. Using find-object as a helper, write
a procedure, (find-and-draw-object!
image objects
name), that finds an object with the given
name and, if it is found, draws it in the image.
If the object is not found, your procedure should raise a reasonable
error.
Exercise 5: Finding Multiple Objects
a. Suppose we inadvertently give two objects in the same list
the same name. For example, suppose we add another entry to the
drawing above of the given form:
(list "tall" "ellipse" "grey" 190 50 150 50)
What do you expect find-object to return
when it is asked to search for "tall"?
b. Check your answer experimentally.
c. Write a new procedure, (find-all-objects
name objects)
Rewrite find-object so that it finds
all the objects with the given name. (If there
are no objects with the name, it should return the empty list.)
Warning! You cannot use assoc
to solve this problem. You will need to write your own recursive
procedure.
Exercise 6: Identifying Shapes by Characteristic
Assume that we are representing objects and drawings as above, with
a drawing consisting of a list of objects, and each object a list
of length seven (name, type, color, left, top, width, height).
a. Write a procedure, (find-ellipses
objects), that finds all the objects in the
list that are ellipses.
b. Write a procedure, (find-objects-by-color color objects), that gets a list
of objects whose color matches color.
c. Use these two procedures together to write an
expression to identify all the red ellipses.
Exercise 7: Preconditions
a. Review the sample implementation of assoc.
(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))))))
b. What do you think that assoc will do if it is given
a list in which each element is a pair, rather than a list? For
example, can we use assoc to search the following list
to determine the first name of a faculty member whose last name you know?
(define math-cs-stats
(list (cons "Walker" "Henry")
(cons "Stone" "John")
(cons "Rebelsky" "Sam")
(cons "Davis" "Janet")
(cons "Coahran" "Marge")
(cons "Moore" "Emily or Tom")
(cons "Wolf" "Royce")
(cons "Chamberland" "Marc")
(cons "Shuman" "Karen")
(cons "French" "Chris")
(cons "Romano" "David")
(cons "Mosley" "Holly")
(cons "Kuiper" "Shonda")))
c. Confirm or refute your answers by experimentation.
d. Based on your experience, what preconditions should
assoc have?
Exercise 8: Using a Specific Database
For some problems, it seems natural to always use a specific database,
rather than to pass the database as a parameter. For example,
suppose we've already set up a large list of colors, such as
named-colors, and don't want the programmer to have to
mention it in her code, perhaps because we don't even want her to know
what we've named it.
For example, consider the following procedure that converts a
color name to an RGB color.
(define cname-to-rgb
(lambda (cname)
(let ((entry (assoc cname named-colors)))
(if entry
(rgb.new (list-ref entry 1) (list-ref entry 2) (list-ref entry 3))
0))))
The strategy of using a specific database in a procedure is often
called hard-coding the database.
a. Using cname-to-rgb, convert off white to an RGB color.
b. Using cname-to-rgb, convert olive green to an RGB
color.
c. Suppose that we wanted to write the converse procedure, one that
given an RGB color, finds the corresponding name. Can we still
hard-code the database? If so, show how. If not, explain why
not.
For Those with Extra Time
Extra 1: Finding Color Names By Components
Write a procedure,
(lookup-color-by-components
r g b),
that takes red, green, and blue components and finds a color which
matches all three components. If you fail to find a color that matches
all three components, return the empty string.
Extra 2: Finding Names By Nearby Components
Write a procedure, (lookup-nearby-colors
r g b),
that takes red, green, and blue components and finds a color each of
whose components is within sixteen of the corresponding component.
If you fail to find a color that matches all three components, return
the empty string.
Extra 3: Finding Multiple Entries
a. What do you expect your procedure to return if given 255, 255, and 255
as parameters?
b. Verify your results experimentally.
c. Rewrite lookup-nearby-colors so that it returns
a list of all the nearby colors, rather than just the first one. Note
that if there are no nearby colors, you should return the empty list.
Extra 4: Finding Entries by Attribute
So far, we haven't used the last part of each entry, the attributes that
someone has assigned to the color. Note that we can get those attributes
by taking the cdr of the cdr of the cdr of the cdr of the entry.
a. Write a procedure, (lookup-colors-by-attribute attribute ctable), that returns a list of entries that contain the given attribute. For example,
> (lookup-colors-by-attribute "bw" named-colors)
(("black 0 0 0 "bw" "web-safe")
("blah grey" 153 153 153 "bw" "web-safe")
("medium grey" 128 128 128 "bw")
("off white" 250 250 250 "bw")
("white" 255 255 255 "bw" "web-safe"))
You may find the following procedure useful.
(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 colors that were both rainbow colors and
web safe. 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.
;;; Procedure:
;;; lookup-color-by-name
;;; Parameters:
;;; cname, a color name
;;; ctable, a list of color entries
;;; Purpose:
;;; Looks up the color in the table.
;;; Produces:
;;; color, an RGB color
;;; Preconditions:
;;; Each entry in ctable must be a list.
;;; Element 0 of each entry must be a string which represents a color name.
;;; Elements 1, 2, and 3 of each entry must be integers which represent
;;; the red, green, and blue components of each color, respectively.
;;; Postconditions:
;;; If an entry for the name appears somewhere in the table, color is
;;; the corresponding RGB color (computed from the components).
;;; If multiple entries with the same name appear in the table, color
;;; is the computed RGB color for one of them.
;;; If no matching entries appear, color is the integer 0 (which is an
;;; alternate name for black).
;;; Does not affect the table.
(define lookup-color-by-name
(lambda (cname ctable)
(let ((assoc-result (assoc cname ctable)))
(if assoc-result
(rgb.new (list-ref assoc-result 1)
(list-ref assoc-result 2)
(list-ref assoc-result 3))
0))))
;;; Value:
;;; named-colors
;;; Type:
;;; List of lists.
;;; Each sublist is of length at least four and contains a name,
;;; red, green, and blue components, and a sequence of attributes.
;;; Each component is an integer between 0 and 255, inclusive.
;;; Everything else is a string.
;;; Contents:
;;; A list of common colors, their components, and some attributes.
(define named-colors
(list (list "black" 0 0 0 "bw" "web-safe")
(list "blah grey" 153 153 153 "bw" "web-safe")
(list "blood red" 102 0 0 "reds" "web-safe")
(list "blue" 0 0 255 "primary" "rainbow" "web-safe")
(list "green" 0 255 0 "primary" "rainbow")
(list "indigo" 102 0 255 "rainbow" "web-safe")
(list "medium grey" 128 128 128 "bw")
(list "off white" 250 250 250 "bw")
(list "orange" 255 119 0 "rainbow")
(list "pale red" 255 240 240 "reds")
(list "red" 255 0 0 "primary" "rainbow" "web-safe" "reds")
(list "violet" 79 47 79 "rainbow")
(list "white" 255 255 255 "bw" "web-safe")
(list "violet red" 204 50 153 "reds")
(list "yellow" 255 255 0 "rainbow" "secondary" "web-safe")))
;;; Procedure:
;;; lookup-color-by-component
;;; Parameters:
;;; component, an integer between 0 and 255, inclusive
;;; position, an integer between 1 and 3, inclusive
;;; ctable, a list of color entries.
;;; Purpose:
;;; Find a color name in the table which has the specified
;;; component (1 for red, 2 for green, 3 for blue).
;;; Produces:
;;; cname, a string (or the value #f)
;;; Preconditions:
;;; Each entry in ctable must be a list.
;;; Element 0 of each entry must be a string which represents a color name.
;;; Elements 1, 2, and 3 of each entry must be integers which represent
;;; the red, green, and blue components of each color, respectively.
;;; Postconditions:
;;; If position is 1 and an entry with the same red value as component
;;; appears somewhere in the table, cname is the name of one such entry.
;;; If position is 2 and an entry with the same green value as component
;;; appears somewhere in the table, cname is the name of one such entry.
;;; If position is 3 and an entry with the same blue value as component
;;; appears somewhere in the table, cname is the name of one such entry.
;;; If no matching entries appear, cname is #f.
;;; Does not affect the table.
(define lookup-color-by-component
(lambda (component pos ctable)
(cond
((null? ctable)
#f)
((equal? component (list-ref (car ctable) position))
(car (car ctable)))
(else
(lookup-color-by-component component position (cdr ctable))))))
