|CSC 153||Grinnell College||Spring, 2005|
|Computer Science Fundamentals|
This laboratory exercise reviews basic elements of vectors within Scheme.
A vector is a collection of elements which are indexed by integers from 0 through n-1, where n is the length of the vector. Furthermore, in Scheme, vectors have the property that any element within a vector may be accessed directly. As an example, consider a list of 10 names and a vector of the same names:
In order to find the seventh name (MacKay) in the list, we must start at the first element and move element-by-element to get the desired item. Within the vector, however, we simply specify the appropriate index (since indexing starts at 0, the seventh item is in position 6).
Just as a string is a sequence of characters enclosed in double quotes ("), a vector is a sequence of elements beginning with #( and ending with ). Thus, the following are valid vectors with four components:
#(2 3/4 -7 3.14179) #(3 #\a "fred" henry)
Chez Scheme also allows a notation where the number of components in a vector is placed between the opening number sign # and the left parenthesis (, as shown below:
#4(2 3/4 -7 3.14179) #4(3 #\a "fred" henry)
The vector? predicate tests whether or not an element is a vector. Some examples are:
(vector? #(2 3/4 -7 3.14179)) ==> #t (vector? #4(3 #\a "fred" henry)) ==> #t (vector? "fred") ==> #f
In addition to explicitly writing out a vector (e.g., the vector literals above), vectors can be constructed with either of two constructor procedures, vector and make-vector.
vector makes a vector out of the elements that follow, as shown in these examples:
(vector 2 3/4 -7 3.14179) (vector 3 #\a "fred" 'henry)
make-vector constructs a vector of a specified length. If a second argument is given, then each component of the new vector contains a copy of the value of the second argument. For example, (make-vector 5) produces a vector with five components, and (make-vector 5 7) generates a vector of 5 elements, each of which contains the number 7. Thus, (make-vector 5 7) produces the vector #5(7 7 7 7 7) .
Once a vector is produced, the vector-length procedure returns its length (its number of components), and vector-ref returns the element in a given position. Some examples follow.
(vector-length #(3 #\a "fred" henry)) ==> 4 (vector-length #()) ==> 0 (vector-ref #(3 #\a "fred" henry) 0) ==> 3 (vector-ref #(3 #\a "fred" henry) 2) ==> "fred" (vector-ref #(3 #\a "fred" henry) 6) ==> error: invalid index
Remember that components of a vector are indexed, beginning with index 0. Thus, 3 is element 0 in the vector #(3 #\a "fred" henry)
The procedures vector->list and list->vector allow us to convert vectors to lists and conversely. Some examples are:
(vector->list #(3 #\a "fred" henry)) ==> (3 #\a "fred" henry) (list->vector '(3 #\a "fred" henry)) ==> #4(3 #\a "fred" henry)
These operations are summarized in the following table:
|Procedure||Sample Call||Result of Example||Comment|
|vector?||(vector? #('a 'b 'c))||#t||Return true (#t) if element is a vector|
|vector||(vector 'a 'b 'c)||#('a 'b 'c)||Make a vector of the parameters|
|make-vector||(make-vector 4)||#(__ __ __ __)||Make an uninitialized vector of the given length|
|make-vector||(make-vector 4 5)||#(5 5 5 5)||Make vector with length, with all components specified|
|vector-length||(vector-length #('a 'b 'c))||3||Return length of given vector|
|vector-ref||(vector-ref #('a 'b 'c) 1)||'b||Return given component of vector|
|vector->list||(vector->list #('a 'b 'c))||('a 'b 'c)||Converts vector to corresponding list|
|list->vector||(list->vector '(a b c))||#3(a b c)||Converts list to corresponding vector|
Now consider the procedure view as follows:
(define view (lambda (vec) ;Pre-condition: vec is a vector ;Post-condition: vec is printed at the keyboard (let ((highest-index (sub1 (vector-length vec)))) (display "#(") (let loop ((i 0)) (display (vector-ref vec i)) (if (< i highest-index) (begin (display " ") (loop (add1 i)))))) (display ")")))
Write a procedure vector-find that searches a vector for a given item. If the item is found, vector-find should return the location of the first occurrence of the item. If the vector is not present, vector-find should return -1.
(vector-find 4 '#(6 2 4 10 -18)) ===> 2 (vector-find 5 '#(6 2 4 10 -18)) ===> -1 (vector-find 'a '#(a b)) ===> 0 (vector-find 'a '#()) ===> -1
Define a higher-order Scheme procedure named
returns a procedure for checking that all elements of a vector satisfy a
specified predicate. That is, given any predicate,
vector-of should return a predicate that takes a vector as
argument and determines whether each of its elements satisfies
((vector-of even?) '#(6 2 4 10 -18)) ===> #t ((vector-of positive?) '#(6 2 4 10 -18)) ===> #f ((vector-of symbol?) '#(a b)) ===> #t ((vector-of real?) '#()) ===> #t
In the reading on sorting and mutation, Scheme's procedure set! was introduced as a means to change the value of a variable. Similarly, procedure vector-set! changes the value stored in a designated location within a vector. The form for vector-set! is:
(vector-set! vect index new-value)
That is, within vector vect, the element at the given index is changed to the specified new-value.
As the following examples indicate, procedure vector-set! itself does not return a new value -- rather it changes parameter vect.
(define x #(3 #\a "fred" 0.31894 12/5)) x (vector-set! x 3 "susan") x (vector-set! x 1 3.141592) x (define f (lambda (y) (vector-set! y 4 15))) (f x) x (vector-set! #(1 2 3 4 5 6) 3 10) (define y #(1 2 3 4 5 6)) (vector-set! y 3 10) y
Again, it is important to emphasize that vector-set! need not return a useful value. (Standard Scheme does not specify what is value returned.) Instead, the vector parameter to vector-set! changes. Further, this change even occurs when vector-set! is applied within another function -- x changes in the call (f x), since f in turn calls vector-set!.
Similarly, procedure vector-fill! changes all components of a given vector to a specified value, as illustrated in the following sequence:
(define x #(3 #\a "fred" 0.31894 12/5)) x (vector-fill! x "henry") x (vector-set! x 3 "terry") x
In this example, note that Chez Scheme uses a shorthand notation when printing a vector, all of whose components are identical. In particular, Chez Scheme prints
to represent a vector of five components, with each component being the string "henry".
If this notation #5("henry") seems confusing, Chez Scheme can provide a more conventional output of vectors. First, type
In subsequent lines, vectors will be printed showing each component.
After using the print-vector-length procedure as shown, try the above sequence (with vector-fill!) to see this alternative output.
To restore the previous format for printing vectors, type
In writing Scheme procedures, it is common to use an exclamation point (!) at the end of a procedure name, when that procedure changes a parameter.
vector-iotathat takes a natural number
nas argument and returns a vector of length
ncontaining all of the natural numbers less than
n, in ascending order.
(vector-iota 9) ===> #9(0 1 2 3 4 5 6 7 8) (vector-iota 2) ===> #2(0 1) (vector-iota 0) ===> #0()
This document is available on the World Wide Web as
created April 3, 1997
last revised February 3, 2005
|For more information, please contact Henry M. Walker at email@example.com.|