Summary: 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: Unlike lists, vectors are indexed and vectors are mutable.

As you've seen in many of the procedures and programs we've written so far, there are many problems in which we have to deal with collections of information. We have now learned one primary technique for representing collections of data: We can represent the collection as a list. But representing a collection as a list has some problems. In particular, it is relatively expensive to get a particular element of a list and it is equally expensive to change a particular element. Why is it expensive to get an element (say, the tenth element)? In the case of a list, we need to cdr through the list until we reach the element. Changing an element may be even worse, because once we've reached the position, we need to build the list (or file) back to a new form. Does this mean that lists and other similar structures are inappropriate ways to represent collections? Certainly not. Rather, they work very well for some purposes (e.g., it is easy to extend a list) and less well for other purposes (e.g., extracting and changing). To resolve these deficiencies, Scheme provides an alternate mechanism for representing collections, the vector.

You may have noted that when we use lists to group data (e.g., the information for a spot or a shape), we need to use list-ref or repeated calls to cdr to get later elements of the list. Unfortunately, list-ref works by cdr'ing down the list. Hence, it takes about five steps to get to the fifth element of the list and about one hundred steps to get to the one hundredth element of a list. Similarly, to get to the fifth element of a file, we'll need to read the preceding elements and to get to the hundredth element, we'll also need to read through the preceding elements. 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). For example, if we need to translate a palette index to the corresponding color, it would be nice if we could look up color number 212 just as fast as color number 0. Vectors address this problem. Vectors contain a fixed number of elements and provide indexed access (also called random 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 or a file: The initial element of a list is immediately accessible, but subsequent elements are increasingly difficult and time-consuming to access.

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; to change a color in a color palette). When we use lists, we essentially need to build a new list to change one element. When we use files, we often have to build a new file, copying both preceding and subsequent values. 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.

When showing a vector, Scheme shows each of its elements, enclosed in parentheses, with an extra character, #, in front of the left parenthesis. For instance, here's how Scheme shows a vector containing the strings "alpha", "beta", and "gamma", in that order: #("alpha" "beta" "gamma") The mesh (also called pound, sharp, or hash) character distinguishes the vector from the list containing the same elements. Some implementations of Scheme permit us to use vector literals, in which a programmer can use a similar syntax to specify a vector when writing a Scheme program or typing commands and definitions into the Scheme interactive interface. In some such implementations, the literal begins with the hash mark. In others, the programmer must place a single quotation mark before the mesh so that Scheme will not try to evaluate the vector as if it were some exotic kind of procedure call. We traditionally recommend that you avoid using this notation just as we recommend that you avoid the corresponding list literal notation for lists.

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

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! #() > (define beta 2) > (vector "alpha" beta (list "gamma" 3) (vector "delta" 4) (vector "epsilon")) #("alpha" 2 ("gamma" 3) #("delta" 4) #("epsilon")) As the last example shows, Scheme vectors, like Scheme lists, can be heterogeneous, containing elements of various types.

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.

The type predicate vector? takes any Scheme value as argument and determines whether it is a vector. > (vector? (vector "alpha" "beta" "gamma")) #t > (vector? (list "alpha" "beta" "gamma")) ; a list, not a vector #f > (vector? "alpha beta gamma") ; a string, not a vector #f

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

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: out of bounds: 3

All of the previous procedures look a lot like list procedures, except that many are more efficient (e.g., vector? and vector-length take a constant number of steps; list? takes a number of steps proportional to the the length of the list and list-ref takes a number of steps proportional to the index). Now let's see a procedure that's much different. We can use procedures to change vectors. 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. As you may recall, 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")) > sample-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 supposed to be immutable: applying vector-set! to such a vector is an error, and the contents of such vectors are therefore constant. (Warning! Some implementations of Scheme, including the ones we use, don't enforce this rule.)

The vector->list procedure 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 (vector 31 27 16)) (31 27 16) > (vector->list (vector)) () > (list->vector (list #\a #\b #\c)) #(#\a #\b #\c) > (list->vector (list 31 27 16)) #(31 27 16)

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")) > sample-vector ; original 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.

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.

Since we are writing this procedure ourselves, we should begin by documenting it. In most implementations, we will need to recurse over the list, adding elements to a corresponding vector. We will also need to build that vector first. Since we only want to build one vector, we should use the husk-and-kernel technique. The husk creates the vector and tells the kernel and then calls the kernel. However, we may need other parameters for the kernel, so it is time to think a little bit about the kernel. Since we want to copy all the elements of the list to the vector, we probably need to repeat some basic step, and the only way we know how to do repetition is recursion. To keep track of what we are copying, we will probably need a counter that we pass to the helper. Let us call that counter pos, since it keeps track of a position in the list or vector. What should we copy from at each step? We could copy the element at position pos of the list into position pos of the vector. However, that is somewhat inefficient because it requires us to step through to the ith element of the list. Since we no longer need a value from the list once we have copied it, we can cdr through the list as we step through the vector. Now, our goal is to copy the initial element of the list into the appropriate position of the vector. When do we stop? When we run out of elements to copy. Given all of the above, here is how to set things up. The kernel is a little bit more complicated. We need to keep track of where we are in the vector. We may also want to carefully specify what this kernel is supposed to do. (Such specification is not always necessary for helpers, but I think it clarifies things in this case.) Is this the only way to write the list->vector procedure? No. More advanced students might know about the apply procedure which makes life significantly easier. (define list->vector (lambda (lst) (apply vector lst))) In other words: Call the vector procedure, giving it the elements of lst as its arguments. Don't worry if you don't understand this now. We will return to the idea later in the semester.

Now let us consider how to go in the opposite direction. Once again, we will probably need to recurse to step through positions and need to keep track of the position with an extra variable. Should we create a list first and then populate it? No. We do not typically mutate lists. So, we will update the list on the fly, adding elements and extending the list at each step. Let's start with the helper. The helper will build a list from a subrange of the vector. Now, we just have to set things up for this kernel. We start at position 0. We end just before the length of the vector. So, here goes ...

Each time we learn a new structure, we learn techniques for recursing over that structure. As the previous examples suggested, recursion over vectors is relatively straightforward, but usually requires that we have a helper procedure that includes additional parameters - the current position in the vector and the length of the vector. (Why do we include the length? So that we don't have to recompute it each time.) The test for the base case is then to check whether the current position equals the length and the simplify step is to add 1 to the position. (define vector-proc (lambda (vec other) (vector-proc-kernel vec other 0 (vector-length vec)))) (define vector-proc-kernel (lambda (vec other pos len) (if (= pos len) (base-case vec other) (combine (vector-ref vec pos) (vector-proc-kernel vec other (+ pos 1) len))))) At times, it's better to start at the end of the vector and work backwards. In this strategy, we get the base case when the position reaches 0 and we simplify by subtracting 1. (define vector-proc (lambda (vec other) (vector-proc-kernel vec other (- (vector-length vec) 1)))) (define vector-proc-kernel (lambda (vec other pos) (if (< pos 0) (base-case vec other) (combine (vector-ref vec pos) (vector-proc-kernel vec other (- pos 1))))))

(list->vector lst) Convert a list to a vector. (vector val_1 ... val_n) Create a vector with the given elements. (vector? val) Determine if val is a vector. (vector-fill vec val) Fill vec with multiple copies of val. (vector-ref vec pos) Extract an element from vec. (vector-set! vec pos val) Set element pos of vec to val. (vector->list vec) Convert a vector to a list.