# Vectors

## Introduction

Vectors are data structures that are very similar to lists in that they arrange data in linear fashion. Vectors differ from lists in two significant ways: vectors are indexed and vectors are mutable.

You may have noted that when we use lists to group data (e.g., the information on a course), we need to use `list-ref` to get latter elements of the list. Unfortunately, `list-ref` works by cdr'ing down the list. It takes about five steps to get to the fifth element of the list. It would be nicer if we could access any element of the group of data in the same amount of time (preferably a small amount of time).

Vectors contain a fixed number of elements and provide random access (also called indexed access) to those elements, in the sense that each element, regardless of its position in the vector, can be recovered in the same amount of time. In this respect, a vector differs from a list: The first element of a list is immediately accessible, but subsequent elements are increasingly difficult and time-consuming to get at.

You may have also noted that we occasionally want to change an element of a group of data (e.g., to change a student's grade in the structure we use to represent that student). When we use lists, we essentially need to build a new list to change one element.

Vectors are mutable data structures: It is possible to replace an element of a vector with a different value, just as one can take out the contents of a container and put in something else instead. It's still the same vector after the replacement, just as the container retains its identity no matter how often its contents are changed.

The particular values that a vector contains at some particular moment constitute its state. One could summarize the preceding paragraph by saying that the state of a vector can change and that state changes do not affect the underlying identity of the vector.

## Displaying Vectors

When displaying a vector, Scheme displays each of its elements, enclosed in parentheses, with an extra character, `#`, in front of the left parenthesis. For instance, here's how Scheme displays a vector containing the symbols `alpha`, `beta`, and `gamma`, in that order:

```#(alpha beta gamma)
```

The mesh (pound, sharp) character distinguishes the vector from the list containing the same elements.

We can use the same syntax to specify a vector when writing a Scheme program or typing commands and definitions into the Scheme interactive interface, except that we have to place a single quotation mark at the beginning, just as we do with list literals, so that Scheme will not try to evaluate the vector as if it were some exotic kind of procedure call. (DrScheme will not make this mistake even if you forget the single quotation mark, but not all implementations of Scheme are so generous.)

In the interaction window, when DrScheme displays a vector as the value of some top-level expression that the user supplied, it does something more ambitious, but potentially rather confusing: It inserts a numeral between the mesh character and the left parenthesis to indicate the number of elements in the vector, thus:

```#3(alpha beta gamma)
```

However, you can instruct DrScheme to use the straight mesh-and-parentheses representation, with no numeral, by giving the following command at the beginning of your program or interactive session:

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

that is, ``Don't print the lengths of vectors''.

## Vector Procedures

Standard Scheme provides the following fundamental procedures for creating vectors and selecting and replacing their elements:

### `vector`

The constructor `vector` takes any number of arguments and assembles them into a vector, which it returns.

```> (vector 'alpha 'beta 'gamma))
#(alpha beta gamma)

> (vector)  ; the empty vector -- no elements!
#()

> (vector 'alpha "beta" '(gamma 3) '#(delta 4) (vector 'epsilon))
#(alpha "beta" (gamma 3) #(delta 4) #(epsilon))
```

As the last example shows, Scheme vectors can be heterogeneous, containing elements of various types, just like Scheme lists.

### `make-vector`

The `make-vector` procedure takes two arguments, a natural number `k` and a Scheme value `obj`, and returns a `k`-element vector in which each position is occupied by `obj`.

```> (make-vector 12 'foo)
#(foo foo foo foo foo foo foo foo foo foo foo foo)

> (make-vector 4 0)
#(0 0 0 0)

> (make-vector 0 4)  ; the empty vector again
#()
```

The second argument is optional; if you omit it, the value that initially occupies each of the positions in the array is left unspecified. Various implementations of Scheme have different ways of filling them up, so you should omit the second argument of `make-vector` only when you intend to replace the contents of the vector right away.

### `vector?`

The type predicate `vector?` takes any Scheme value as argument and determines whether it is a vector.

```> (vector? '#(alpha beta gamma))
#t

> (vector? '(alpha beta gamma))  ; a list, not a vector
#f

> (vector? "alpha beta gamma")  ; a string, not a vector
#f

> (vector? '#(#f))  ; a one-element vector (the element is #f)
#t
```

### `vector-length`

The `vector-length` procedure takes one argument, which must be a vector, and returns the number of elements in the vector.

```> (vector-length (vector 3 1 4 1 5 9))
6

> (vector-length (vector 'alpha 'beta 'gamma))
3

> (vector-length (vector))
0
```

### `vector-ref`

The selector `vector-ref` takes two arguments -- a vector `vec` and a natural number `k` (which must be less than the length of `vec`). It returns the element of `vec` that is preceded by exactly `k` other elements. (In other words, if `k` is 0, you get the element that begins the vector; if k is 1, you get the element after that; and so on.)

```> (vector-ref (vector 3 1 4 1 5 9) 4)
5

> (vector-ref (vector 'alpha 'beta 'gamma) 0)
alpha

> (vector-ref (vector 'alpha 'beta 'gamma) 3)
vector-ref: index 3 out of range [0, 2] for vector: #(alpha beta gamma)
```

### `vector-set!`

The mutator `vector-set!` takes three arguments -- a vector `vec`, a natural number `k` (which must be less than the length of `vec`), and a Scheme value `obj` -- and replaces the element of `vec` that is currently in the position indicated by `k` with `obj`. This changes the state of the vector irreversibly; there is no way to find out what used to be in that position after it has been replaced. It is a Scheme convention to place an exclamation point meaning ``Proceed with caution!'' at the end of the name of any procedure that makes such an irreversible change in the state of an object.

The value returned by `vector-set!` is unspecified; one calls `vector-set!` only for its side effect on the state of its first argument.

```> (define sample-vector (vector alpha beta gamma delta epsilon))

> (vector-set! sample-vector 2 'zeta)

> sample-vector  ; same vector, now with changed contents
#(alpha beta zeta delta epsilon)

> (vector-set! sample-vector 0 "foo")

> sample-vector  ; changed contents again
#("foo" beta zeta delta epsilon)

> (vector-set! sample-vector 2 -38.72)

> sample-vector  ; and again
#("foo" beta -38.72 delta epsilon)
```

Vectors introduced into a Scheme program by means of the mesh-and-parentheses notation are ``immutable'' -- applying `vector-set!` to such a vector is an error, and the contents of such vectors are therefore constant. (Some implementations of Scheme, including DrScheme, don't enforce this rule.)

### `vector->list`

The `vector->list` takes any vector as argument and returns a list containing the same elements in the same order; the `list->vector` procedure performs the converse operation.

```> (vector->list '#(31 27 16))
(31 27 16)

> (vector->list (vector))
()

> (list->vector '(#\a #\b #\c))
#(#\a #\b #\c)

> (list->vector (list 31 27 16))
#(31 27 16)
```

### `vector-fill!`

The `vector-fill!` procedure takes two arguments, the first of which must be a vector. It changes the state of that vector, replacing each of the elements it formerly contained with the second argument.

```> (define sample-vector (vector 'rho 'sigma 'tau 'upsilon))

> (vector-fill! sample-vector 'kappa)

> sample-vector  ; same vector, now with changed contents
#(kappa kappa kappa kappa)
```

The `vector-fill!` procedure is invoked only for its side effect and returns an unspecified value.

## Implementing Standard Proceudres

Some older implementations of Scheme may lack the `list->vector`, `vector->list`, and `vector-fill!` procedures, but it is straightforward to define them in terms of the others:

```(define our-list->vector
(lambda (ls)
(apply vector ls)))
```

In other words: Call the `vector` procedure, giving it the elements of `ls` as its arguments.

```(define our-vector->list
(lambda (vec)
(let kernel ((remaining (vector-length vec))
(result '()))
(if (zero? remaining)
result
(let ((position (- remaining 1)))
(kernel position (cons (vector-ref vec position) result)))))))
```

In other words: Let `remaining` initially be the number of elements in the vector. This parameter is used to keep track of how many elements of the vector remain to be transferred to the list. Let `result` initially be the empty list. We shall add the elements of the vector, one by one, to `result`. If there are no more elements to be transferred, return the finished list `result`; otherwise, let `position` be one less than `remaining`, so that it indicates the position in the vector that is occupied by the rightmost element that has not yet been transferred. Select that element from the vector (with `vector-ref` and add it to the beginning of the `result` list (with `cons`); then start over again, reducing the number of elements remaining by 1.

```(define our-vector-fill!
(lambda (vec obj)
(let ((size (vector-length vec)))
(let kernel ((position 0))
(if (< position size)
(begin
(vector-set! vec position obj)
(kernel (+ position 1))))))))
```

In other words: Let `size` be the number of elements in the vector `vec`. Starting at position 0, put `obj` into each position within `vec`, overwriting the value previously stored in that position. Increase `position` by 1 after each such overwriting step. When `position` becomes equal to `size`, stop. (Since the `if`-expression has no alternate, an unspecified value is returned at the end of the process. Since `vector-fill!` is invoked only for its side effect, the value it returns is insignificant.)

## Other Vector Procedures

With these procedures, we can write many other vector operations. For example, here is a procedure that generates vectors using a procedure to generate each element.

```;;; Procedure:
;;;   vector-generator
;;; Parameters:
;;;   A unary procedure
;;;   A size
;;; Purpose:
;;;   Creates a vector of the appropriate size by applying
;;;   the procedure to the values 0 .. size-1.
;;; Preconditions:
;;;   The procedure must take exactly one argument, a number.
;;;     [Unverified]
;;;   The size must be a nonnegative integer. [Unverified]
;;; Postconditions:
;;;   Returns a new vector.
(define vector-generator
(lambda (proc size)
(let ((result (make-vector size)))
(let kernel ((position 0))
(if (= position size)
result
(begin
(vector-set! result position (proc position))
(kernel (+ position 1)))))))))
```

The following `double-every-element` procedure takes one argument, a vector `vec` of numbers, and returns a new vector just like `vec` except that each of the elements is twice the corresponding element of `vec`.

```;;; Procedure:
;;;   double-every-element
;;; Parameters:
;;;   A vector
;;; Purpose:
;;;   Creates a new vector by doubling every element in the original
;;;   vector.
;;; Produces:
;;;   A vector of the same length as the parameter.
;;; Preconditions:
;;;   The vector contains only numbers.
;;; Postconditions:
;;;   Has not changed the vector parameter.
(define double-every-element
(lambda (vec)
(let* ((size (vector-length vec))
(result (make-vector size)))
(let kernel ((position 0))
(if (= position size)
result
(begin
(vector-set! result position (* 2 (vector-ref vec position)))
(kernel (+ position 1))))))))

> (double-every-element '#(3 1 4 1 5 9))
#(6 2 8 2 10 18)
```

In English: Let `size` be the length of the vector `vec`, and let `result` be a new vector of the same length (contents unspecified). Start at position 0. If the position number is equal to `size`, all of the elements of `vec` have already been processed; return the `result` vector. Otherwise, double the element stored in the current position of `vec` and put the doubled number into the corresponding position in `result`; then proceed to the next position.

An alternative definition of `double-every-element` uses `vector-generator`:

```(define double-every-element
(lambda (vec)
(let ((double (lambda (x) (* x 2))))
(vector-generator (compose double (left-section vector-ref vec))
(vector-length vec)))))
```

(I haven't rechecked this alternative definition to make sure that it works.)

A third definition of `double-every-element` uses `map` and the conversion procedures.

```(define double-every-element
(lambda (vec)
(list->vector
(map (lambda (x) (* x 2))
(vector->list vec)))))
```

## History

November 7, 1997 (John Stone and/or Henry Walker)

• Created

April 5, 2000 (John Stone)

• Last revised

Wednesday, 20 September 2000 (Sam Rebelsky)

Wednesday, 6 November 2000 (Sam Rebelsky)

• Updated.
• Reformatted.