CSC151.01 2009F Functional Problem Solving : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Summary: In this laboratory, you will explore various aspects of the Vector data type that Scheme provides as an alternative to lists.
Open the reference on vectors in a new tab or window.
a. In the Interaction pane, type in a vector literal that denotes a vector containing just the two elements 3.14159 and 2.71828. How does MediaScript display the value of this vector?
b. Create a vector that contains the same two values by using the
vector
procedure.
c. Create a vector that contains the same two values by using the
make-vector
and vector-set!
procedures.
Consider the following code. (That is, read it, don't enter it.)
>
(define aardvark (list 1 2 3 4))
>
(define baboon aardvark)
>
(define aardvark (cons 5 (cdr aardvark)))
>
(define chinchilla (vector 1 2 3 4))
>
(define dingo chinchilla)
>
(vector-set! chinchilla 0 5)
a. What do you expect the output of the following commands to be?
>
(list-ref aardvark 0)
_____>
(list-ref baboon 0)
_____
b. Verify your answer experimentally. (That is, you can type in the commands now.)
c. What do your results suggest about Scheme?
d. What do you expect the output of the following commands to be? (That is, think about the answer; don't just type it in.)
>
(vector-ref chinchilla 0)
_____>
(vector-ref dingo 0)
_____
e. Verify your answer experimentally. (You can type the commands now.)
f. What do your results suggest about vectors and lists in Scheme?
In the reading on vectors, we saw that it was possible
to implement list->vector
and
vector->list
by using more primitive
operations (particularly vector-set!
and
vector-length
).
Here's the definition of list->vector
and its kernel.
;;; Procedure: ;;; list->vector ;;; Parameters: ;;; lst, a list. ;;; Purpose: ;;; Convert the list to a vector. ;;; Produces: ;;; vec, a vector ;;; Preconditions: ;;; lst is a list ;;; Postconditions: ;;; vec is a vector. ;;; The length of vec equals the length of lst. ;;; The ith element of vec equals the ith element of lst for ;;; all "reasonable" i. (define list->vector (lambda (lst) (list->vector-kernel! lst ; Copy the whole list 0 ; Starting at position 0 (make-vector (length lst) null) ; Into a new vector of the appropriate length ))) ;;; Procedure: ;;; list->vector-kernel! ;;; Parameters: ;;; lst, a list to copy ;;; pos, a position in the vector ;;; vec, a vector ;;; Purpose ;;; Copy values from lst into positions pos, pos+1, ... ;;; Produces: ;;; vec, the same vector but with different contents. ;;; Preconditions: ;;; The length of vec = pos + the length of list. [Unverified] ;;; pos >= 0. [Unverified] ;;; Postconditions: ;;; Element pos of vec now contains element 0 of list. ;;; Element pos+1 of vec now contains element 1 of lst. ;;; Element pos+2 of vec now contains element 2 of lst. ;;; ... ;;; The last element of vec now contains the last element of lst. (define list->vector-kernel! (lambda (lst pos vec) ; We don't bother to verify the preconditions because this ; procedure should only be called by something that has already ; verified the preconditions (explicitly or implicitly). (cond ; If there's nothing left to copy, stop. ((null? lst) vec) ; Otherwise, copy the initial element of the list and ; then copy the remaining elements (else (vector-set! vec pos (car lst)) (list->vector-kernel! (cdr lst) (+ pos 1) vec)))))
The design of list->vector
is a bit
subtle. Explain what the kernel does. If you're not completely
sure, you may want to add a call to display
to the kernel, as in
(display (list 'l2v-kernel! lst pos vec)) (newline)
It is possible to represent a collection of colors (a “palette”) as a vector. Why would we do so? Well, once we've chosen a palette, we can represent an image as a collection of indices into that palette. Such a representation is typically much more compact than representing each color with the full RGB triplet.
For example, here is a palette that represents the colors in the rainbow.
(define rainbow-palette (list->vector (map color->rgb (list "red" "orange" "yellow" "green" "blue" "indigo" "violet"))))
Write a procedure, (
, that, given a vector of
RGB colors, makes each color in the palette slightly darker. (You will
not build a new vector. Rather, you will replace
each color by the darker version.
palette-darker!
palette
)
You can test your procedure by converting the vector back to a list and then converting the RGB colors back to strings
>
(palette-darker! rainbow-palette)
>
(map rgb->string (vector->list rainbow-palette))
Here is a procedure that builds a list-based palette from an image by
randomly selecting n
values from the image.
;;; Procedure: ;;; palette-maker ;;; Parameters: ;;; image, an image ;;; n, a positive integer ;;; Purpose: ;;; Create a palette (a list of colors) of size n by selecting ;;; colors from image. ;;; Produces: ;;; palette, a list of RGB colors ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; palette contains colors that resemble (or are equal to) some of ;;; the colors in image. (define palette-maker (lambda (image n) (let ((width (image-width image)) (height (image-height image))) (let kernel ((i n) (palette null)) (if (zero? i) palette (kernel (- i 1) (cons (image-get-pixel image (random width) (random height)) palette)))))))
Using this procedure as a guide to creating colors, and
list->vector
as a guide to building
vectors, write (
,
which fills palette-fill!
palette
image
)palette
with colors randomly selected
from the image. (Why don't we have an n
as
a parameter? Because you should use the palette size for the number
of colors to fill in.)
Write a procedure, (
, which takes one argument,
a vector of numbers, and returns the sum of the elements of that vector.
vector-sum
numbers
)
You can use vector->list
from the reading as
a pattern for vector-sum
;
only a few judicious changes are needed. However, you should
not use vector->list
as a helper.
;;; Procedure: ;;; vector->list ;;; Parameters: ;;; vec, a vector ;;; Purpose: ;;; Builds a list that contains the elements of vec in the same order. ;;; Produces: ;;; lst, a new list. ;;; Preconditions: ;;; [None] ;;; Postconditions: ;;; The element at position i of lst is the element at position ;;; i of vec for all reasonable i. ;;; Does not change vec. (define vector->list (lambda (vec) (vector->list-kernel vec 0 (vector-length vec)))) ;;; Procedure: ;;; vector->list-kernel ;;; Parameters: ;;; vec, a vector ;;; start, an integer ;;; finish, an integer ;;; Purpose: ;;; Builds a list that contains elements start ... finish-1 of vec ;;; Produces: ;;; lst, a new list. ;;; Preconditions: ;;; start >= 0 ;;; finish >= start ;;; finish <= length of vec ;;; Postconditions: ;;; The element at position i of lst is the element at position ;;; i+start of vec for all reasonable i. ;;; Does not change vec. (define vector->list-kernel (lambda (vec start finish) ; We stop at the finish. (if (= start finish) ; There are no more elements to put into a list, so use ; the empty list. null ; Otherwise, add the element at position start to a list of ; the remaining elements. (cons (vector-ref vec start) (vector->list-kernel vec (+ 1 start) finish)))))
Write your own version of vector-fill!
. Remember that
vector-fill!
takes two parameters, a vector and a value,
and puts that value in every position of the vector.
Note: You may find that you want to do two things for a particular
position: fill the value at that position and recurse. Remember that
when you want to sequence actions if a test succeeds, you should use
a cond
rather than an if
.
Write a procedure, (
that rotates the elements in
vector-rotate!
vec
)vec
. That is, rotate!
puts the
initial element of vec
at the end, the element
at position 1 in position 0, the element at position 2 in position 1,
and so on and so forth.
a. Write a procedure, (
, that creates a new vector
whose elements appear in the reverse order of the elements in
vector-reverse
vec
)vec
.
b. Write a procedure,
(vector-reverse!
,
that reverses vec
)vec
“in place”.
That is, instead of producing a new vector, it rearranges the elements
within vec
.
Write a procedure, (
,
that rotates the values in vector-rotate!
vec
amt
)vec
by
amt
positions. That is, the first
amt
values in vec
move
to the end, the value in position amt
moves to
position 0, the value in position amt
+1 moves
to position 1, and so on and so forth.
Write a procedure, (
, that takes one argument,
a vector of colors, and returns the darkest color in that vector.
You can assume that every position in the vector contains a color.
palette-darkest
palette
)
You will need the definitions of rgb-brightness
and
rgb-darker-of-two
.
;;; Procedure: ;;; rgb-brightness ;;; Parameters: ;;; color, an RGB color ;;; Purpose: ;;; Computes the brightness of color on a 0 (dark) to 100 (light) scale. ;;; Produces: ;;; b, an integer ;;; Preconditions: ;;; color is a valid RGB color. That is, each component is between ;;; 0 and 255, inclusive. ;;; Postconditions: ;;; If color1 is likely to be perceived as lighter than color2, ;;; then (brightness color1) > (brightness color2). ;;; 0 <= b <= 100 (define rgb-brightness (lambda (color) (round (* 100 (/ (+ (* 0.30 (rgb-red color)) (* 0.59 (rgb-green color)) (* 0.11 (rgb-blue color))) 255))))) ;;; Procedure: ;;; rgb-darker-of-two ;;; Parameters: ;;; color1, an RGB color. ;;; color2, an RGB color. ;;; Purpose: ;;; Find the darker of color1 and color2. ;;; Produces: ;;; darker, an RGB color. ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; darker is either color1 or color2 ;;; (rgb-brightness darker) <= (rgb-brightness color1) ;;; (rgb-brightness darker) <= (rgb-brightness color2) (define rgb-darker-of-two (lambda (color1 color2) (if (< (rgb-brightness color1) (rgb-brightness color2)) color1 color2)))
In a number of previous exercises, you wrote procedures that iterated
over the vector, changing values as you went. (For example,
vector-fill!
and palette-complement!
both had this form.) Summarize the form of a procedure that recurses
over vectors, setting the value at each position to a new value.
Just as in the case of list->vector
, you will probably
want to define a helper procedure that fills only part of the vector.
Your termination condition will certainly be different and should probably
involve the length of the vector.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009F (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.