One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.
Copyright © 2011
Jay Reynolds Freeman,
all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
In Scheme, a vector is an object that can store a bunch of other Scheme objects, in much the same manner as a list. In fact, if you only looked at a description of what Scheme vectors do, you might wonder why anyone would bother with them: There is nothing you can do with vectors that you can't do with lists. You can put things into vectors, and get them out, and a few other things besides, but you can do all of those things just as well with lists. Furthermore, there are some things you can do with lists that you cannot do very well at all with vectors. So, why vectors?
With vectors, you can do some things faster than with lists. The main purpose of vectors to make programs run faster. If you are not worried about making your programs run faster, you can skip this tutorial for now. Just remember that vectors can help speed things up, and come back here later, when you need to.
I will spare you a detailed discussion of why vectors are faster, but a general idea might be useful. Scheme accesses data in lists by starting at the front and going down the list, one cons cell at a time, until it finds the cons cell it wants. The longer the list, the more cons cells there are, and the longer that process takes. Vectors, on the other hand, are systematically laid out in Scheme memory in such a way that if Scheme is looking for a particular element in the vector -- say the nth from the beginning -- it can calculate just where that element is going to be, and look there immediately, without having to deal with a whole lot of cons cells on the way. That process is faster than going down a list one cons cell at a time.
By the way, the process of going through a list one cons cell at a time has an informal name. Lisp programmers call it cdring down a list, in which "cdring" is pronounced to rhyme with "ruddering".
Vectors print out like lists, only there is a "#" character in front of the whole thing. You use a "#" character when you are creating a vector by quoting, too. The next example shows how closely similar the quoted forms of lists and vectors are.
(define my-list '(1 2 3)) ;; ==> my-list my-list ;; ==> (1 2 3) (define my-vector '#(1 2 3)) ;; ==> my-vector my-vector ;; ==> #(1 2 3)
You can also create vectors with a procedure application. Remember that you can create lists with "list". Procedure "vector" works just like "list".
(vector 1 2 3) ;; ==> #(1 2 3)
There is also a procedure called "make-vector".
(make-vector 4) ;; ==> (() () () ()) (make-vector 4 "Nuts!") ;; ==> ("Nuts!" "Nuts!" "Nuts!" "Nuts!")
Procedure "make-vector" takes one or two arguments. The first argument is the length of the vector, which is four in the examples just given. That is one thing about vectors that is different from lists; You must specify the length of a vector at the time it is created, and there is no way to change it afterward. The specification can be implicit, as in the case of quoted vectors -- the vector in the earlier example obviously had a length of three -- or explicit, as in the first argument to "make-vector".
If "make-vector" has only one argument, then it will fill up the resulting vector with the empty list; the empty list will be used for each item in the vector created. If "make-vector" has a second argument, that argument will be used for every item in the vector.
If you already have a vector and want to fill all of its elements with one value, you can use "vector-fill!".
(define my-vector (make-vector 5)) ;; ==> my-vector my-vector ;; ==> (() () () () ()) (vector-fill! my-vector 42) ;; ==> #t my-vector ;; ==> (42 42 42 42)
There is another useful way to create a vector. You can make one out of a list, using procedure "list->vector".
(list->vector '(foo "bar" (1 2 3) #t)) ;; ==> #(foo "bar" (1 2 3) #t)
The name "list->vector" is sometimes pronounced "list-to-vector".
Procedure "vector->list" performs the reverse operation.
(vector->list '#(foo "bar" (1 2 3) #t)) ;; ==> (foo "bar" (1 2 3) #t)
These two procedures are very useful when dealing with vectors.
You cannot put things into a vector by "cons", you cannot get at its contents by "car", "cdr", and the other procedures like them, and you cannot alter its contents by "set-car!" and "set-cdr". Those procedures do not work on vectors. You can retrieve content from a vector by using "vector-ref", which stands for "vector reference". It works analogously to "list-ref", and -- like "list-ref" -- it is zero-based when it comes to figuring out which element of a vector is which. Compare the two:
(define l '("peanut" "butter" "sandwich")) ;; ==> l (list-ref l 0) ;; ==> "peanut" (list-ref l 1) ;; ==> "butter" (list-ref l 2) ;; ==> "sandwich" (define v '#("peanut" "butter" "sandwich")) ;; ==> v (vector-ref v 0) ;; ==> "peanut" (vector-ref v 1) ;; ==> "butter" (vector-ref v 2) ;; ==> "sandwich"
You can change the contents of a vector by using "vector-set!", which has no analogy among the standard Scheme procedures for lists. It has side effects -- it changes the vector -- so its name follows the Scheme convention for such things, and ends with an exclamation point. Since "vector-set!" is used solely for the sake of those side effects, it returns only #t. The first two arguments of "vector-set!" are as for "vector-ref", and the third is the new value to go in the specified place in the vector.
(define dinner (vector "tuna" "fish" "sandwich")) ;; ==> dinner dinner ;; ==> #("tuna" "fish" "sandwich") (vector-set! dinner 0 "jelly") ;; ==> #t dinner ;; ==> #("jelly" "fish" "sandwich")
Note the use of "vector" in the preceding example. I could not have written
(define dinner '#("tuna" "fish" "sandwich")) ;; ==> dinner
and then gone on with the example, because vectors defined by quoting are constant: Scheme won't let you change them. If I had done that, there would have been an error message when "vector-set!" tried to substitute "jelly" for "tuna". Procedure "vector" builds a new vector from the content of the list that is its argument, and that new vector is not constant, so the example works.
There is a predicate, "vector?" to tell whether objects are vectors or not, and a procedure, "vector-length", to tell how many items are in a vector.
(vector? '#(1 2 3)) ;; ==> #t (vector? '(1 2 3)) ;; ==> #f (vector? 42) ;; ==> #f (vector-length '#("jelly" "fish" "sandwich")) ;; ==> 3
If you are using a vector for something and find out that it is too short, what do you do? There is no way to change the length of a vector after it is created, so you have to make a new one. There is a simple trick for doing so, that is rather clumsy, but works. You use "vector->list" to make a list containing the vector's content, then append that list together with a new list containing as many items as you need extra spaces in the vector, then use "list->vector" to make a vector from the result. Here are all the steps for that written out individually, using temporary variables for clarity. Suppose we need three more items in a vector, and that we want those spaces to be at the end of the vector, not at the beginning.
(define old-vector '#(1 2 3 4)) ;; ==> old-vector old-vector ;; #(1 2 3 4) (define listified-vector (vector->list old-vector)) ;; ==> listified-vector listified-vector ;; ==> (1 2 3 4) (define list-of-three ;; Note trick for making lists. (vector->list (make-vector 3))) ;; ==> list-of-three list-of-three ;; ==> (() () ()) (define longer-list (append listified-vector list-of-three)) ;; ==> longer-list longer-list ;; ==> (1 2 3 4 () () ()) (define new-vector (list->vector longer-list)) ;; ==> new-vector new-vector ;; ==> #(1 2 3 4 () () ())
An experienced Schemer would very likely have written that without all the temporary variables, for the sake of brevity, perhaps as
(define old-vector '#(1 2 3 4)) ;; ==> old-vector (define new-vector (list->vector (append (vector->list old-vector) (vector->list (make-vector 3))))) ;; ==> new-vector new-vector ;; ==> #(1 2 3 4 () () ())
The multi-line definition of "new-vector" actually is quite easy to read, because of the careful use of indentation to show its structure. We start with two lists that are made out of vectors.
(vector->list old-vector) (vector->list (make-vector 3))
We append them together, being very careful to balance our parentheses.
(append (vector->list old-vector) (vector->list (make-vector 3)))
We convert the resulting list back into a vector, being very careful to balance our parentheses.
(list->vector (append (vector->list old-vector) (vector->list (make-vector 3))))
Finally, we wrap "define" around the whole thing, being very careful to balance our parentheses.
(define new-vector (list->vector (append (vector->list old-vector) (vector->list (make-vector 3)))))
In case you didn't happen to notice, we were always very careful to balance our parentheses. Seriously, leaving parentheses unbalanced by mistake is always an irritating error, and can occasionally result in code that does something other than what you were expecting.
In most programming languages, it is the custom to write source code with structure shown by indentation, as in the preceding example. It would be well worth your while to adopt some similar style -- you don't have to copy mine -- and to make a habit of using it. You might also note that many of the text editors that programmers like to use can be set up to auto-indent -- to indent automatically -- as you type, so that your code comes out sensibly indented without you having to type the extra spaces or tabs yourself. What is more, automatic indentation can draw your attention to unbalanced parentheses before they lift up their tiny heads and bite you.
Even if you forget the rest of this tutorial, remember one basic fact about vectors: The use of vectors instead of lists may allow programs to run faster, particularly when you use long vectors instead of long lists.
-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)