So how do we program with vectors if they're not recursive like lists? While it is true that vectors, being fixed, are not recursive, there is something about them that is: their length. The length of a vector is a natural number, and as we discovered at the start of the quarter, natural numbers are recursive!
This gives us our strategy for programming on vectors: we begin with the length of the vector, and step through each element of the vector until we reach 0.
(: vector-sum (-> (Vectorof Real) Real))
;; Sum elements of the vector
(define (vector-sum numv)
(local
{(define len (vector-length numv))
(: sum (-> Integer Real))
(define (sum i)
(if (< i 0)
0
(+ (vector-ref numv i)
(sum (sub1 i)))))}
(sum (sub1 len))))
What we have just written here is what in many other programming languages would be considered a loop:
(< i 0),
i at each iteration is (sub1 i), and
i is set to (sub1 len), where len is the length of our vector.
Here is a fun exercise: our current loop begins at the right end of the vector (i.e. 1 less than its length) and works towards the left end, at 0. Can you rewrite this function so that it goes from left to right instead?
Here's another observation: what we've just written is just a right fold over a vector. With the power of higher-order programming, we can generalize this:
(: vector-foldr (All (A B) (-> (-> A B B) B (Vectorof A) B)))
;; Fold elements of vector according to given function
(define (vector-foldr f z v)
(local
{(define len (vector-length v))
(: fold (-> Integer B))
(define (fold i)
(if (< i 0)
z
(f (vector-ref v i)
(fold (sub1 i)))))}
(fold (sub1 len))))
Just like lists, we can append two vectors together.
(: vector-append (All (A) (-> (Vectorof A) (Vectorof A) (Vectorof A))))
An interesting thing to think about is whether this is any better than appending two lists. Recall that appending a list took longer than we thought because it was easy to overlook the fact that we needed to find the end of one list. This means traversing at least one of the lists.
Now suppose we have two vectors. Again, vectors need to have contiguous blocks of memory reserved for them. This means that in order to combine two vectors, we would need to first create a new, larger block of memory to hold the combined vector. But more than that, we would need to copy the values from both old vectors to the new location. This sounds like a lot of work, and it is: since we must copy all of the values, we do about the same amount of work as we did in traversing a list.
This discussion of copying vectors over suggests another complication with working with them. With lists (and everything we've been working with so far), every time we "modified" a list, we were really creating new ones. This is not an issue because it's really a matter of hooking up the lists (i.e. changing the address to the "next" list) in the right way. Because values are always being created, we say that the values we've been working with are immutable.
However, because of how vectors are stored, this isn't really viable: every time we want to change something about a vector, it would mean blocking off a chunk of memory and copying the values over. This where the idea of mutation becomes important. Rather than creating new values when the values change, we can modify existing values instead.
To do this for a vector, we use the function vector-set!:
(: vector-set! (All (A) (-> (Vectorof A) Integer A Void)))
The function vector-set! uses a ! in the name to denote that the function is a function that causes side effects, by convention. We note that the function takes a vector, an integer for which element we want to change, and the value we want to update, but it produces no value.
To indicate that the function does not produce a value, its output type is Void. You may recall this from other functions like display or from complaints by the type checker that your cond expression is missing an else branch.
We can make use of this when we start looking at another higher-order function, map. Recall that map creates a new list by applying a function to each element of a given list. Of course, we can come up with a very straightforward version of this for vectors (see vector-map).
However, if we know that the type of the vector won't change (i.e. our function is a function $f: A \to A$) and we don't need to keep the original vector around, we have the option to change the vector. In other words, instead of creating a new vector, we can replace the values $x$ of our existing vector with the mapped values $f(x)$.
We will call this function vector-map!:
(: vector-map! (All (A) (-> (-> A A) (Vectorof A) Void)))
;; Replace vector of values x with values (f x)
(define (vector-map! f v)
(local
{(define len (vector-length v))
(: vmap (-> Integer Void))
(define (vmap i)
(if (< i 0)
(void)
(begin (vector-set! v i (f (vector-ref v i)))
(vmap (sub1 i)))))}
(vmap (sub1 len))))
Recall that begin is a function that allows us to evaluate several expressions in sequence. The output of a begin expression is the value of the final expression in the sequence. Note that in this case, the final expression is an application of vector-set!, which has no output. This means that if we run this function, it produces no value. Unlike everything else we've done in this class, it appears that evaluating this function does nothing at all! It is not until we peek in at our vector that we notice that it has changed.
One big caveat to this particular function is the requirement that our mapping maps $A$s to $A$s. The usual map can take $A$s to $B$s, which can pose a problem if our vector is mutable: if we've already said that our vector is of type $A$, then we can't change it to a vector of type $B$.
One of the things that we can do with vectors that we couldn't do with lists is have fast access to arbitrary elements in the vector. So performing binary search on a vector makes much more sense than it does on a list.
(: binary-search (-> Integer (Vectorof Integer) (Optional Integer)))
;; Produces the location in the array of the given element,
;; if it is present
(define (binary-search n v)
(local
{(define len (vector-length v))
(: bs (-> Integer Integer (Optional Integer)))
(define (bs l r)
(if (<= l r)
(local
{(define m (exact-floor (/ (+ l r) 2)))}
(cond
[(< (vector-ref v m) n) (bs (add1 m) r)]
[(> (vector-ref v m) n) (bs l (sub1 m))]
[else (Some m)]))
'None))}
(bs 0 (sub1 len))))