A First Look at Vectors

Next: Accumulating Knowledge Up: Intermezzo 5 The Cost of Previous: The Definition of ``on

A First Look at Vectors

Until now we have paid little attention to how much time it takes to retrieve data from structures or lists. Now that we have a tool for stating general judgments, let's take a close look at this basic computation step. Recall the last problem of the preceding part: finding a route in a graph. The program find-route requires two auxiliaries: find-route/list and neighbors. We paid a lot of attention to find-route/list and none to neighbors. Indeed, developing neighbors was just an exercise (see ), because looking up a value in a list is by now a routine programming task.

Here is a possible definition for neighbors:

;; neighbors : node graph -> (listof node)
;; to lookup the node in graph 
(define (neighbors node graph) 
  (cond 
    [(empty? graph) (error 'neighbors ``can't happen'')] 
    [else (cond 
            [(symbol=? (first (first graph)) node) (second (first graph))] 
            [else (neighbors node (rest graph))])]))

The function is similar to contains-doll? and has roughly the same behavior. More concretely, neighbors is O(N) when we assume that graph is a list of N nodes.

Considering that neighbors is used at every stage of the evaluation of find-route, neighbors is possibly a bottleneck. As a matter of fact, if the route we are looking for involves N nodes (the maximum), neighbors is applied N times, so the algorithm requires steps in neighbors.

In contrast to lists, structures deal with value extractions as a constant time operation. At first glance this observation seems to suggest that we use structures as representations of graphs. A closer look, however, shows that this idea doesn't work easily. The graph algorithm works best if we are able to work with the names of nodes and access a node's neighbors based on the name. A name could be a symbol or the node's number in the graph. In general, what we really wish to have in a programming language is

a class of compound values size with constant lookup time,
based on ``keys.''

Because the problem is so common, Scheme and most other languages offer at least one built-in solution.

Here we study the class of vectors. A vector is a well-defined mathematical class of data with specific basic operations. For our purposes, it suffices to know how to construct them, how to extract values, and how to recognize them:

The operation vector is like list. It consumes an arbitrary number of values and creates a compound value from them: a vector. For example, (vector V-0 ... V-n) creates a vector from V-0 through V-n.
DrScheme also provides a vector analogue to build-list. It is called build-vector. Here is how it works:
```
(build-vector N f) = (vector (f 0) ... (f (- N 1)))
```
That is, build-vector consumes a natural number N and a function f on natural numbers. It then builds a vector of N items by applying f to 0, ..., N-1.
The operation vector-ref extracts a value from a vector in constant time, that is, for i between 0 and n (inclusive):
```
(vector-ref (vector V-0 ... V-n) i) = V-i
```
In short, extracting values from a vector is O(1).
If vector-ref is applied to a vector and a natural number that is smaller than 0 or larger than n, vector-ref signals an error.
The operation vector-length produces the number of items in a vector:
```
(vector-length (vector V-0 ... V-n)) = (+ n 1)
```
The operation vector? is the vector-predicate:
```
(vector? (vector V-0 ... V-n)) = true
(vector? U) = false 
```
if U is a value that isn't created with vector.

We can think of vectors as functions on a small, finite range of natural numbers. Their range is the full class of Scheme values. We can also think of them as tables that associate a small, finite range of natural numbers with Scheme values. Using vectors we can represent graphs like those in figures and if we use numbers as names. For example:

Using this translation, we can also produce a vector-based representation of the graph in figure :

(define Graph-as-list
  '((A (B E)) 
    (B (E F)) 
    (C (D)) 
    (D ()) 
    (E (C F)) 
    (F (D G)) 
    (G ())))

(define Graph-as-vector
  (vector (list 1 4) 
          (list 4 5) 
          (list 3) 
          empty 
          (list 2 5) 
          (list 3 6) 
          empty))

The definition on the left is the original list-based representation; the one on the right is a vector representation. The vector's i-th field contains the list of neighbors of the i-th node.

The data definitions for node and graph change in the expected manner. Let's assume that N is the number of nodes in the given graph:

A node is an natural number between 0 and N-1.

A graph is a vector of nodes: (vectorof (listof node)).

The notation (vectorof X) is similar to (listof X). It denotes a vector that contains items from some undetermined class of data X.

Now we can redefine neighbors:

;; neighbors : node graph -> (listof node)
;; to lookup the node in graph 
(define (neighbors node graph) 
  (vector-ref graph node))

As a result, looking up the neighbors of a node becomes a constant-time operation, and we can truly ignore it when we study the abstract running time of find-route.

Exercises

Exercise 29.3.1

Test the new neighbors function. Use the strategy of section to formulate the tests as boolean expressions. Solution

Exercise 29.3.2

Adapt the rest of the find-route program to the new vector representation. Adapt the tests from exercises through to check the new program.

Measure how much time the two find-route programs consume to compute a route from node A to node E in the graph of figure . Recall that (time expr) measures how long it takes to evaluate expr. It is good practice to evaluate expr, say, 1000 times when we measure time. This produces more accurate measurements. Solution

Exercise 29.3.3

Translate the cyclic graph from figure into our vector representation of graphs. Solution

Before we can truly program with vectors, we must understand the data definition. The situation is comparable to that when we first encountered lists. We know that vector, like cons, is provided by Scheme, but we don't have a data definition that directs our program development efforts.

So, let us take a look at vectors. Roughly speaking, vector is like cons. The cons primitive constructs lists, the vector primitive creates vectors. Since programming with lists usually means programming with the selectors first and rest, programming with vectors must mean programming with vector-ref. Unlike first and rest, however, vector-ref requires manipulating the vector and an index into a vector. This suggests that programming with vectors really means thinking about indices, which are natural numbers.

Let's look at some simple examples to confirm this abstract judgment. Here is the first one:

;; vector-sum-for-3 : (vector number number number) -> number
(define (vector-sum-for-3 v) 
  (+ (vector-ref v 0) 
     (vector-ref v 1) 
     (vector-ref v 2)))

The function vector-sum-for-3 consumes vectors of three numbers and produces their sum. It uses vector-ref to extract the three numbers and adds them up. What varies in the three selector expressions is the index; the vector remains the same.

Consider a second, more interesting example: vector-sum, a generalization of vector-sum-for-3. It consumes an arbitrarily large vector of numbers and produces the sum of the numbers:

;; vector-sum : (vectorof number) -> number
;; to sum up the numbers in v 
(define (vector-sum v) ...)

Here are some examples:

(= (vector-sum (vector -1 3/4 1/4))
   0)

(= (vector-sum (vector .1 .1 .1 .1 .1 .1 .1 .1 .1 .1)) 
   1)

(= (vector-sum (vector)) 
   0)

The last example suggests that we want a reasonable answer even if the vector is empty. As with empty, we use 0 as the answer in this case.

The problem is that the one natural number associated with v, its length, is not an argument of vector-sum. The length of v is of course just an indication of how many items in v are to be processed, which in turn refers to legal indices of v. This reasoning forces us to develop an auxiliary function that consumes the vector and a natural number:

;; vector-sum-aux : (vectorof number) N -> number
;; to sum up the numbers in v relative to i  
(define (vector-sum-aux v i) ...)

The natural choice for the initial value of i is the length of v, which suggests the following completion of vector-sum:

(define (vector-sum v) 
  (vector-sum-aux v (vector-length v)))

Based on this definition, we can also adapt the examples for vector-sum to vector-sum-aux:

(= (vector-sum-aux (vector -1 3/4 1/4) 3)
   0)

(= (vector-sum-aux (vector .1 .1 .1 .1 .1 .1 .1 .1 .1 .1) 10) 
   1)

(= (vector-sum-aux (vector) 0) 
   0)

Unfortunately, this doesn't clarify the role of the second argument. To do that, we need to proceed to the next stage of the design process: template development.

When we develop templates for functions of two arguments, we must first decide which of the arguments must be processed, that is, which of the two will vary in the course of a computation. The vector-sum-for-3 example suggests that it is the second argument in this case. Because this argument belongs to the class of natural numbers, we follow the design recipe for those:

(define (vector-sum-aux v i) 
  (cond 
    [(zero? i) ...] 
    [else ... (vector-sum-aux v (sub1 i)) ...]))

Although we considered i to be the length of the vector initially, the template suggests that we should consider it the number of items of v that vector-sum-aux must consider and thus as an index into v.

The elaboration of i's use naturally leads to a better purpose statement for vector-sum-aux:

;; vector-sum-aux : (vectorof number) N -> number
;; to sum up the numbers in v with index in [0, i) 
(define (vector-sum-aux v i) 
  (cond 
    [(zero? i) ...] 
    [else ... (vector-sum-aux v (sub1 i)) ...]))

Excluding i is natural because it is initially (vector-length v) and thus not an index.

;; vector-sum : (vectorof number) -> number
;; to compute the sum of the numbers in v 
(define (vector-sum v) 
  (vector-sum-aux v (vector-length v)))

;; vector-sum-aux : (vectorof number) N -> number
;; to sum the numbers in v with index in [0, i) 
(define (vector-sum-aux v i) 
  (cond 
    [(zero? i) 0] 
    [else (+ (vector-ref v (sub1 i)) 
             (vector-sum-aux v (sub1 i)))]))

Figure: Summing up the numbers in a vector (version 1)

;; lr-vector-sum : (vectorof number) -> number
;; to sum up the numbers in v 
(define (lr-vector-sum v) 
  (vector-sum-aux v 0))

;; vector-sum : (vectorof number) -> number 
;; to sum up the numbers in v with index in [i, (vector-length v)) 
(define (vector-sum-aux v i) 
  (cond 
    [(= i (vector-length v)) 0] 
    [else (+ (vector-ref v i) (vector-sum-aux v (add1 i)))]))

Figure: Summing up the numbers in a vector (version 2)

To transform the template into a complete function definition, we consider each clause of the cond:

If i is 0, there are no further items to be considered because there are no vector fields between 0 and i with i excluded. Therefore the result is 0.
Otherwise, (vector-sum-aux v (sub1 i)) computes the sum of the numbers in v between 0 and (sub1 i) [exclusive]. This leaves out the vector field with index (sub1 i), which according to the purpose statement must be included. By adding (vector-ref v (sub1 i)), we get the desired result:
```
(+ (vector-ref v (sub1 i)) (vector-sum-aux v (sub1 i)))
```

See figure

for the complete program.

If we were to evaluate one of the examples for vector-sum-aux by hand, we would see that it extracts the numbers from the vector in a right to left order as i decreases to 0. A natural question is whether we can invert this order. In other words: is there a function that extracts the numbers in a left to right order?

The answer is to develop a function that processes the class of natural numbers below (vector-length v) and to start at the first feasible index: 0. Developing this function is just another instance of the design recipe for variants of natural numbers from section . The new function definition is shown in figure . The new auxiliary function now consumes 0 and counts up to (vector-length v). A hand-evaluation of

(lr-vector-sum (vector 0 1 2 3))

shows that vector-sum-aux indeed extracts the items from v from left to right.

The definition of lr-vector-sum shows why we need to study alternative definitions of classes of natural numbers. Sometimes it is necessary to count down to 0. But at other times it is equally useful, and natural, to count from 0 up to some other number.

The two functions also show how important it is to reason about intervals. The auxiliary vector-processing functions process intervals of the given vector. A good purpose statement specifies the exact interval that the function works on. Indeed, once we understand the exact interval specification, formulating the full function is relatively straightforward. We will see the importance of this point when we return to the study of vector-processing functions in the last section.

Exercises

Exercise 29.3.4

Evaluate (vector-sum-aux (vector -1 3/4 1/4) 3) by hand. Show the major steps only. Check the evaluation with DrScheme's stepper. In what order does the function add up the numbers of the vector?

Use a local-expression to define a single function vector-sum. Then remove the vector argument from the inner function definition. Why can we do that? Solution

Exercise 29.3.5

Evaluate (lr-vector-sum (vector -1 3/4 1/4)) by hand. Show the major steps only. Check the evaluation with DrScheme's stepper. In what order does the function add up the numbers of the vector?

Use a local-expression to define a single function lr-vector-sum. Then remove those arguments from the inner function definition that remain the same during an evaluation. Also introduce definitions for those expressions that always evaluate to the same value during the evaluation. Why is this useful? Solution

Exercise 29.3.6

The list-based analogue of vector-sum is list-sum:

;; list-sum : (listof number) -> number 
;; to compute the sum of the numbers on alon 
(define (list-sum alon) 
  (list-sum-aux alon (length alon)))

;; list-sum-aux : N (listof number) -> number  
;; to compute the sum of the first L numbers on alon 
(define (list-sum-aux L alon) 
  (cond 
    [(zero? L) 0] 
    [else (+ (list-ref alon (sub1 L)) (list-sum-aux (sub1 L) alon))]))

Instead of using the structural definition of the list, the developer of this program used the size of the list--a natural number--as the guiding element in the design process.

The resulting definition uses Scheme's list-ref function to access each item on the list. Looking up an item in a list with list-ref is an O(N) operation for lists of N items. Determine the abstract running time of sum (from section ), vector-sum-aux and list-sum-aux. What does this suggest about program development? Solution

Exercise 29.3.7

Develop the function norm, which consumes a vector of numbers and produces the square root of the sum of the squares of its numbers. Another name for norm is distance-to-0, because the result is the distance of a vector to the origin, when we interpret the vector as a point. Solution

Exercise 29.3.8

Develop the function vector-contains-doll?. It consumes a vector of symbols and determines whether the vector contains the symbol 'doll. If so, it produces the index of 'doll's field; otherwise, it produces false.

Determine the abstract running time of vector-contains-doll? and compare with that of contains-doll?, which we discussed in the preceding subsection.

Now discuss the following problem. Suppose we are to represent a collection of symbols. The only interesting problem concerning the collection is to determine whether it contains some given symbol. Which data representation is preferable for the collection: lists or vectors? Why? Solution

Exercise 29.3.9

Develop the function binary-contains?. It consumes a sorted vector of numbers and a key, which is also a number. The goal is to determine the index of the key, if it occurs in the vector, or false. Use the binary-search algorithm from section .

Determine the abstract running time of binary-contains? and compare with that of contains?, the function that searches for a key in a vector in the linear fashion of vector-contains-doll?.

Suppose we are to represent a collection of numbers. The only interesting problem concerning the collection is to determine whether it contains some given number. Which data representation is preferable for the collection: lists or vectors? Why? Solution

Exercise 29.3.10

Develop the function vector-count. It consumes a vector v of symbols and a symbol s. Its result is the number of s that occur in v.

Determine the abstract running time of vector-count and compare with that of count, which counts how many times s occurs in a list of symbols.

Suppose we are to represent a collection of symbols. The only interesting problem concerning the collection is to determine how many times it contains some given symbol. Which data representation is preferable for the collection: lists or vectors? Why? What do exercises , , and this exercise suggest? Solution

While accessing the items of a vector is one kind of programming problem, constructing vectors is an entirely different problem. When we know the number of items in a vector, we can construct it using vector. When we we wish to write programs that work on a large class of vectors independent of their size, however, we need build-vector.

Consider the following simple example. Suppose we represent the velocity of an object with a vector. For example, (vector 1 2) represents the velocity of an object on a plane that moves 1 unit to the right and 2 down in each time unit. For comparison, (vector -1 2 1) is the veloicity of an object in space; it moves -6 units in the x direction in 6 time units, 12 units in the y direction in 6 time units, and 6 units in the z direction in 6 time units. We call (vector -6 12 6) the displacement of the object in 6 time units.

Let's develop a function that computes the displacement for an object with some velocity v in t time units:

;; displacement : (vectorof number) number -> (vectorof number)
;; to compute the displacement of v and t 
(define (displacement v t) ...)

Computing the displacement is straightforward for some examples:

(equal? (displacement (vector 1 2) 3) 
        (vector 3 6))

(equal? (displacement (vector -1 2 1) 6) 
        (vector -6 12 6))

(equal? (displacement (vector -1 -2) 2) 
        (vector -2 -4))

We just multiply each component of the object with the number, which yields a new vector.

The examples' meaning for our programming problem is that displacement must construct a vector of the same length as v and must use the items in v to compute those of the new vectors. Here is how we build a vector of the same how-many as some given vector v:

(build-vector (vector-length v) ...)

Now we need to replace ... with a function that computes the 0-th, 1-st, and so on items of the new vector:

;; new-item : N -> number
;; to compute the contents of the new vector at the i-th position 
(define (new-item index) ...)

Following our discussion, we multiply (vector-ref v i) with t and that's all.

Take a look at the complete definition:

;; displacement : (vectorof number) number -> (vectorof number)
;; to compute the displacement of v and t 
(define (displacement v t) 
  (local ((define (new-item i) (* (vector-ref v i) t))) 
    (build-vector (vector-length v) new-item)))

The locally defined function is not recursive. We can thus replace it with a plain lambda-expression:

;; displacement : (vectorof number) number -> (vectorof number)
;; to compute the displacement of v and t 
(define (displacement v t) 
  (build-vector (vector-length v) (lambda (i) (* (vector-ref v i) t))))

Mathematicians call this function scalar product. They have also studied many other operations on vectors, and in Scheme we can develop those in a natural manner.

Exercises

Exercise 29.3.11

Develop the function id-vector, which consumes a natural number and produces a vector of that many 1's. Solution

Exercise 29.3.12

Develop the functions vector+ and vector-, which compute the pointwise sum and differences of two vectors. That is, each consumes two vectors and produces a vector by manipulating corresponding programs. Assume the given vectors are of the same how-many. Also develop the functions checked-vector+ and checked-vector-. Solution

Exercise 29.3.13

Develop the function distance, which consumes two vectors and computes their distance. Think of the distance of two vectors as the length of the line between them. Solution

Exercise 29.3.14

Develop a vector representation for chessboards of size for n in N. Then develop the following two functions on chessboards:

;; build-board : N (N N -> boolean) -> board
;; to create a board of size n x n,  
;; fill each position with indices i and j with (f i j) 
(define (build-board n f) ...)

;; board-ref : board N N -> boolean 
;; to access a position with indices i, j on a-board 
(define (board-ref a-board i j) ...)

Can we now run the program of section

using vectors instead of lists? Inspect the solution of exercises

and

. Solution

Exercise 29.3.15

A matrix is a chessboard of numbers. Use the chessboard representation of exercise to represent the matrix

displaymath73174

Using build-board, develop the function transpose, which creates a mirror image of the matrix along its diagonal from the upper-left corner to the lower-right one. For example, the given matrix turns into

displaymath73176

More generally, the item at (i,j) becomes the item at (j,i). Solution

Next: Accumulating Knowledge Up: Intermezzo 5 The Cost of Previous: The Definition of ``on

PLT