CSC 153 Grinnell College Spring, 2005 Computer Science Fundamentals Laboratory Exercise

# Vectors

## Goals

This laboratory exercise reviews basic elements of vectors within Scheme.

## The Vector Concept

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).

## Representation of Vectors in Scheme

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
```

## Constructing Vectors

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) .

## Accessor Procedures

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)

## Conversion Procedures

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 " ")

(display ")")))

```
1. Run view on several vector examples (such as those appearing earlier in this lab) to check what this procedure does.

2. Write a paragraph explaining how view works.

3. As already noted, Chez Scheme prints a number after the initial # symbol in a symbol, indicating how many elements are present in a vector. Modify view, so that it also prints this length.

4. 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
```
5. Define a higher-order Scheme procedure named `vector-of` that returns a procedure for checking that all elements of a vector satisfy a specified predicate. That is, given any predicate, `pred?`, `vector-of` should return a predicate that takes a vector as argument and determines whether each of its elements satisfies `pred?`.

```((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
```

## Modifying Vectors

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.

1. Type in the following sequence, and explain what is returned at each step:
```
(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

```
#5("henry")
```

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

```
(print-vector-length #f)
```

In subsequent lines, vectors will be printed showing each component.

1. 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

```
(print-vector-length #t)
```

### Convention

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.

1. Review the examples for vector-fill!, and write a couple of sentences explaining the result of each Scheme command.

2. Define a Scheme procedure named `vector-iota` that takes a natural number `n` as argument and returns a vector of length `n` containing 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

```http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-vectors.shtml
```