Functional Problem Solving (CSC 151 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: In today's laboratory, you will experiment with association lists, structures that make it easy to look up information. You will work with two kinds of association lists: lists of color information, as described in the reading, and lists of shape descriptions, similar to the drawings we encountered earlier in the course.
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.
c. In the interactions pane, create a new 200x200 image and take note of its image number.
d. In the definitions pane, write a definition to assign the name
canvas
to the number of the image you created. For example,
if you just created image 3, you would write
(define canvas 3)
a. Write 6-P documentation for a procedure,
(
, that lets you find the attributes
associated with a particular color.
lookup-attributes
color-name
color-table
)
For example,
>
(lookup-attributes "yellow" named-colors)
'("rainbow" "secondary" "web-safe")
>
(lookup-attributes "Oregon salmon" named-colors)
#f
>
(lookup-attributes "off white" named-colors)
'("bw")
>
(lookup-attributes "green" named-colors)
'("primary" "rainbow")
You may wish to consult the documentation for
and
assoc
to guide you.
lookup-color-by-name
b. Write the procedure
.
lookup-attributes
Hint: You should rely on assoc
to do the searching. Your goal is primarily to extract the attributes
once you've found the appropriate entry.
Hint: The goal of this procedure is similar to the goal
of lookup-color-by-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.
Let's explore an association list that uses values other than colors.
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)))
In the code for this lab, you'll see a procedure named
image-draw-named-object!
, which can be used
to render these objects.
a. Copy the definition of drawing
to the definitions
pane (and be sure to make an appropriate citation). Then, using image-draw-named-object!
and
assoc
, write an expression
that tells the GIMP to draw the object named "bc"
from
drawing
.
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.
Using assoc
and image-draw-named-object!
as helpers, write a
procedure, (
, 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.
find-and-draw-object!
image
objects
name
)
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 assoc
to return
when it is asked to search for "tall"
?
b. Check your answer experimentally.
c. Write a new procedure,
(
, that produces a list with
all the objects with the given name. (If there
are no objects with the name, it should return the empty list.)
find-all-objects
name
objects
)
Warning! You cannot use assoc
to solve this problem. You will need to write your own recursive
procedure.
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, (
, that finds all the objects in the
list that are ellipses.
find-ellipses
objects
)
b. Write a procedure, (
, that gets a list
of objects whose color matches find-objects-by-color
color
objects
)color
.
c. Use these two procedures together to write an expression to identify all the red ellipses.
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 color-name-to-rgb (lambda (color-name) (let ((entry (assoc color-name 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 color-name-to-rgb
, convert off white to an RGB color.
b. Using color-name-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.
Write a procedure,
(
,
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.
lookup-color-by-components
r
g
b
)
Write a procedure, (
,
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.
lookup-nearby-colors
r
g
b
)
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.
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, (
, that returns a list of entries that contain the given attribute. For example,
lookup-colors-by-attribute
attribute
ctable
)
>
(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.
;;; 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 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.