More Practice with Vectors

Programming with mutable vectors is hardly ever needed in the kinds of programs that we encountered. Still, because it is far more prevalent in conventional languages, it is an important skill and deserves more practice than section  suggests. This section covers sorting with vectors, but its goal is to practice reasoning about intervals when processing vectors.

We encountered the idea of sorting as early as section , where we designed the sort function. It consumes a list of numbers and produces a list of numbers with the same items in sorted (ascending or descending) order. An analogous function for vectors consumes a vector and produces a new vector. But, using vector mutation, we can also design a function that changes the vector so that it contains the same items as before, in a sorted order. Such a function is called an IN-PLACE SORT because it leaves all the items inside the existing vector.

An in-place-sort function relies exclusively on effects on its input vector to accomplish its task:

;; in-place-sort : (vectorof number) -> void
;; effect: to modify V such that it contains the same items  
;; as before but in ascending order  
(define (in-place-sort V) ...) 

(local ((define v1 (vector 7 3 0 4 1)))
  (begin 
    (in-place-sort v1) 
    (equal? v1 (vector 0 1 3 4 7)))) 

The standard template for a vector-processing function uses an auxiliary function:

(define (in-place-sort V)
  (local ((define (sort-aux V i) 
            (cond 
              [(zero? i) ...] 
              [else 
                ... (vector-ref V (sub1 i)) ... 
                ... (sort-aux V (sub1 i)) ...]))) 
    (sort-aux V (vector-length V)))) 

Recall that the key to designing functions such as sort-aux is to formulate a rigorous purpose and/or effect statement. The statement must clarify on which interval of the possible vector indices the function works and what exactly it accomplishes. One natural effect statement follows:

;; sort-aux : (vectorof number) N -> void
;; effect: to sort the interval [0,i) of V in place  
(define (sort-aux V i) ...) 

(local ((define v1 (vector 7 3 0 4 1)))
  (begin 
    (sort-aux v1 5) 
    (equal? v1 (vector 0 1 3 4 7)))) 

(local ((define v1 (vector 7 3 0 4 1)))
  (begin 
    (sort-aux v1 4) 
    (equal? v1 (vector 0 3 4 7 1)))) 

;; in-place-sort : (vectorof number) -> void ;; effect: to modify V such that it contains the same items ;; as before but in ascending order (define (in-place-sort V) (local (;; sort-aux : (vectorof number) N -> void ;; effect: to sort the interval [0,i) of V in place (define (sort-aux V i) (cond [(zero? i) (void)] [else (begin ;; sort the segment [0,(sub1 i)): (sort-aux V (sub1 i)) ;; insert (vector-ref V (sub1 i)) into the segment ;; [0,i) so that it becomes sorted'' (insert (sub1 i) V))])) ;; insert : N (vectorof number) -> void ;; to place the value in the i-th into its proper place ;; in the segement [0,i] of V ;; assume: the segment [0,i) of V is sorted (define (insert i V) ...)) (sort-aux V (vector-length V)))) Figure: An in-place sort function: First part

Now we can analyze each case in the template of sort-aux:

1. If i is 0, the interval of the effect statement is [0,0). This means that the interval is empty and that the function has nothing to do.
2. The second clause in the template contains two expressions:

   (vector-ref V (sub1 i))
   ;and 
   (sort-aux V (sub1 i)) 
   

   The first reminds us that we can use the i-1-st field of V; the second one reminds us of the natural recursion. In this case, the natural recursion sorts the interval [0,(sub1 i)). To finish the task, we must insert the value of the i-1-st field into its proper place in the interval [0,i).

   The above examples make this case concrete. When we evaluate (sort-aux v1 4), the number in the last field of v1 remains at its place. The first four items in the vectors are: 0, 3, 4, and 7. To sort the entire interval [0,5), we must insert 1, which is (vector-ref V (sub1 5)), between 0 and 3.

Figure  gathers what we have discussed about in-place-sort so far. It also includes a specification of insert, the second auxiliary function. To understand its effect statement, we reformulate the example for the second clause of sort-aux:

(local ((define v1 (vector 0 3 4 7 1)))
  (begin 
    (insert 4 v1) 
    (equal? v1 (vector 0 1 3 4 7)))) 

Let's look at a second example for insert:

(local ((define v1 (vector 7 3 0 4 1)))
  (begin 
    (insert 1 v1) 
    (equal? v1 (vector 3 7 0 4 1)))) 

(define (in-place-sort V) (local (;; sort-aux : (vectorof number) N -> void ;; effect: to sort the interval [0,i) of V in place (define (sort-aux V i) ...) ;; insert : N (vectorof number) -> void ;; to place the value in the i-th into its proper place ;; in the [0,i] segement of V (define (insert i V) (cond [(zero? i) (void)] [else (cond [(> (vector-ref V (sub1 i)) (vector-ref V i)) (begin (swap V (- i 1) i) (insert (sub1 i) V))] [else (void)])])) ;; swap : (vectorof X) N N void (define (swap V i j) (local ((define temp (vector-ref V i))) (begin (vector-set! V i (vector-ref V j)) (vector-set! V j temp))))) (sort-aux V (vector-length V)))) Figure: An in-place sort function: Second part

Now take a look at the template for insert:

(define (insert i V) 
  (cond 
    [(zero? i) ...] 
    [else 
      ... (vector-ref V (sub1 i)) ... 
      ... (insert (sub1 i) V) ... ])) 

1. If i is 0, the goal is to insert (vector-ref V 0) into the segment [0,0]. Since this interval contains only one number, insert has accomplished its task.
2. If i is positive, the template implies that we may consider another item in V, namely (vector-ref V (sub1 i)), and that we can perform a natural recursion. The immediate question is whether (vector-ref V (sub1 i)) is smaller or larger than (vector-ref V i), the item that is to be moved around. If so, V is sorted on the entire interval [0,i], because V is sorted on [0,i) by assumption. If not, the item at i is out of order still.

   The cond-expression that employs the necessary conditions is

   (cond
     [(> (vector-ref V (sub1 i)) (vector-ref V i)) ...] 
     [(<= (vector-ref V (sub1 i)) (vector-ref V i)) (void)]) 
   

   The second clause contains (void) because there is nothing left to do. In the first clause, insert must--at a minimum--swap the values in the two fields. That is, insert must place (vector-ref V i) into field (sub1 i) and (vector-ref V (sub1 i)) into field i. But even that may not be enough. After all, the value in the i-th field may have to wander over several fields as the first example demonstrated. Fortunately, we can easily solve this problem with the natural recursion, which inserts the (vector-ref V (sub1 i)) into its proper place in [0,(sub1 i)] after the swapping has taken place.

Exercise 43.1.1

Test the auxiliary functions for in-place-sort from figures  and . Formulate the tests as boolean-valued expressions.

Develop and test more examples for in-place-sort.

Integrate the pieces. Test the integrated function. Eliminate superflous arguments from the auxiliary programs in the integrated definition, step by step, testing the complete function after each step. Finally, change in-place-sort so that its result is the modified vector. Solution

Figure: Inserting an item into a sorted vector segment

Exercise 43.1.2

The insert function of figure  performs two vector mutations for each time the function recurs. Each of these mutations pushes (vector-ref V i), for the original value of i, to the left in V until its proper place is found.

Figure  illustrates a slightly better solution. The situation in the top row assumes that the values a, b, and c are properly arranged, that is,

(< a b ... c)

(< a d b)

Develop a function insert that implements its desired effect according to this description. Hint: The new function must consume d as an additional argument. Solution

Exercise 43.1.3

For many other programs, we could swap the order of the subexpressions in begin-expressions and still get a working program. Let's consider this idea for sort-aux:

 
;; sort2-aux : (vectorof number) N -> void 
(define (sort2-aux V i) 
  (cond 
    [(zero? i) (void)] 
    [else (begin 
            (insert2 (sub1 i) V) 
            (sort2-aux V (sub1 i)))])) 

				i-1
				a
left					right

The depicted vector consists of three pieces: a, the item in field (sub1 i), the left fragment, and the right fragment. The questions are which of the two fragments is sorted and into which fragment a should be inserted.

Considering that sort2-aux decreases its first argument and thus sweeps over the vector from right to left, the answers are that the right fragment is initially empty and thus sorted in ascending order by default; the left fragment is still unordered; and a must be inserted into its proper place in the right fragment.

Develop a precise effect statement for sort-aux based on these observations. Then develop the function insert2 so that sort2-aux sorts vectors properly. Solution

In section , we got to know qsort, a function based on generative recursion. Given a list, qsort constructs a sorted version in three steps:

1. choose an item from the list, call it pivot;
2. create two sublists: one with all those items strictly smaller than pivot, another one with all those items strictly larger than pivot;
3. sort each of the two sublists, using the same steps, and then append the two lists with the pivot item in the middle.

a vector fragment with pivot item p: left   right p sm-1 la-1 sm-2 sm-3 la-2 partitioning the vector fragment into two regions, separated by p left1   right1   left2 right2 sm-2 sm-1 sm-3 p la-1 la-2 Figure: The partitioning step for in-place quick-sort

Figure  illustrates how this idea can be adapted for an in-place version that works on vectors. At each stage, the algorithm works on a specific fragment of the vector. It picks the first item as the pivot item and rearranges the fragment so that all items smaller than the pivot appear to the left of pivot and all items larger than pivot appear to its right. Then qsort is used twice: once for the fragment between left1 and right1 and again for the fragment between left2 and right2. Because each of these two intervals is shorter than the originally given interval, qsort eventually encounters the empty interval and stops. After qsort has sorted each fragment, there is nothing left to do; the partitioning process has arranged the vector into fragments of ascending order.

Here is the definition of qsort, an in-place sorting algorithm for vectors:

;; qsort : (vectorof number) -> (vectorof number)
;; effect: to modify V such that it contains the same items as before, 
;; in ascending order  
(define (qsort V) 
  (qsort-aux V 0 (sub1 (vector-length V))))

;; qsort-aux : (vectorof number) N N -> (vectorof number) 
;; effect: sort the interval [left,right] of vector V 
;; generative recursion 
(define (qsort-aux V left right) 
  (cond 
    [(>= left right) V] 
    [else (local ((define new-pivot-position (partition V left right))) 
            (begin (qsort-aux V left (sub1 new-pivot-position)) 
                   (qsort-aux V (add1 new-pivot-position) right)))])) 

The definition of qsort-aux closely follows the algoritm's description. If left and right describe a boundary of size 1 or less, its task is done. Otherwise, it partitions the vector. Because the partitioning step is a separate complex process, it requires a separate function. It must have both an effect and a result proper, the new index for the pivot item, which is now at its proper place. Given this index, qsort-aux continues to sort V on the intervals [left,(sub1 new-pivot-position)] and [(add1 new-pivot-position), right]. Both intervals are at least one item shorter than the original, which is the termination argument for qsort-aux.

Naturally, the key problem here is the partitioning step, which is implemented by partition:

;; partition : (vectorof number) N N -> N
;; to determine the proper position p of the pivot-item  
;; effect: rearrange the vector V so that  
;; - all items in V in [left,p) are smaller than the pivot item 
;; - all items of V in (p,right] are larger than the pivot item 
(define (partition V left right) ...) 

finding the swapping points for partition: left right p sm-1 la-1 sm-2 sm-3 la-2 new-left new-right swapping the items and recuring on a new interval:   left   right p sm-1 sm-3 sm-2 la-1 la-2 stopping the generative recursion and clean-up:   left   right p sm-1 sm-3 sm-2 la-1 la-2   new-right new-left Figure: The partitioning process for in-place quick-sort

The best strategy is to consider an example and to see how the partitioning step could be accomplished. The first example is a small vector with six numbers:

(vector 1.1 0.75 1.9 0.35 0.58 2.2)

(vector 1.1 0.75 0.58 0.35 1.9 2.2)

Figure  illustrates the swapping process that we just described. First, we must find two items to swap. To do that, we search V for the first item to the right of left that is larger than the pivot item. Analogously, we search V for the first item to the left of right that is smaller than the pivot item. These searches yield two indices: new-left and new-right. Second, we swap the items in fields new-left and new-right. The result is that the item at new-left is now smaller than the pivot item and the one at new-right is larger. Finally, we can continue the swapping process with the new, smaller interval. When the first step yields values for new-left and new-right that are out of order, as in the bottom row of figure , then we have a mostly partitioned vector (fragment).

Working through this first example suggests that partition is an algorithm, that is, a function based on generative recursion. Following our recipe, we must ask and answer four questions:

1. What is a trivially solvable problem?
2. What is a corresponding solution?
3. How do we generate new problems that are more easily solvable than the original problem? Is there one new problem that we generate or are there several?
4. Is the solution of the given problem the same as the solution of (one of) the new problems? Or, do we need to perform an additional computation to combine these solutions before we have a final solution? And, if so, do we need anything from the original problem data?

Let's study question 2 with some examples. We stopped working on the first example when the vector had been changed to

(vector 1.1 0.75 0.58 0.35 1.9 2.2)

(<= new-right new-left)

(vector 0.35 0.75 0.58 1.1 1.9 2.2)

Before we accept this seemingly simple solution, let's check it with some additional examples, especially vector fragments where the pivot item is the largest or smallest item. Here is one such example:

(vector 1.1 0.1 0.5 0.4)

Our process clearly yields 3 for new-right. After all, 0.4 is smaller than pivot. The search for new-left, though, works differently. Since none of the items in the vector is larger than the pivot item, it eventually generates 3 as an index, which is the largest legal index for this vector. At this point the search must stop. Fortunately, new-left and new-right are equal at this point, which implies that the partitioning process can stop and means that we can still swap the pivot item with the one in field new-right. If we do that, we get a perfectly well-partitioned vector:

(vector 0.4 0.1 0.5 0.4 1.1)

The third sample vector's items are all larger than the pivot item:

(vector 1.1 1.2 3.3 2.4)

In short, the examples suggest several things:

1. The termination condition for partition is (<= new-right new-left).
2. The value of new-right is the final position of the pivot item, which is in the original left-most point of the interval of interest. It is always acceptable to swap the contents of the two fields.
3. The search for new-right starts at the right-most boundary and continues until it either finds an item that is smaller than the pivot item or until it hits the left-most boundary.
4. Dually, the search for new-left starts at the left-most boundary and continues until it either finds an item that is larger than the pivot item or until it hits the right-most boundary.

We can now gradually translate our discussion into Scheme. First, the partitioning process is a function of not just the vector and some interval, but also of the original left-most position of the vector and its content. This suggests the use of locally defined functions and variables:

(define (partition V left right)
  (local ((define pivot-position left) 
          (define the-pivot (vector-ref V left)) 
          (define (partition-aux left right) 
            ...)) 
    (partition-aux left right))) 

Second, the auxiliary function consumes an interval's boundaries. It immediately generates a new pair of indices from these boundaries: new-left and new-right. As mentioned, the searches for the two new boundaries are complex tasks and deserve their own functions:

;; find-new-right : (vectorof number) number N N [>= left] -> N
;; to determine an index i between right and left (inclusive) 
;; such that (< (vector-ref V i) the-pivot) holds 
(define (find-new-right V the-pivot right left) ...)

;; find-new-left : (vectorof number) number N N [<= right] -> N 
;; to determine an index i between left and right (inclusive) 
;; such that (> (vector-ref V i) the-pivot) holds 
(define (find-new-left V the-pivot left right) ...) 

(define (partition V left right)
  (local ((define pivot-position left) 
          (define the-pivot (vector-ref V left)) 
          (define (partition-aux left right) 
            (local ((define new-right (find-new-right V the-pivot right left)) 
                    (define new-left (find-new-left V the-pivot left right))) 
              ... ))) 
    (partition left right))) 

;; partition : (vectorof number) N N -> N ;; to determine the proper position p of the pivot-item ;; effect: rearrange the vector V so that ;; - all items in V in [left,p) are smaller than the pivot item ;; - all items of V in (p,right] are larger than the pivot item ;; generative recursion (define (partition V left right) (local ((define pivot-position left) (define the-pivot (vector-ref V left)) (define (partition-aux left right) (local ((define new-right (find-new-right V the-pivot right left)) (define new-left (find-new-left V the-pivot left right))) (cond [(>= new-left new-right) (begin (swap V pivot-position new-right) new-right)] [else ; (< new-left new-right) (begin (swap V new-left new-right) (partition-aux new-left new-right))])))) (partition left right))) ;; find-new-right : (vectorof number) number N N [>= left] -> N ;; to determine an index i between right and left (inclusive) ;; such that (< (vector-ref V i) the-pivot) holds ;; structural recursion: see text (define (find-new-right V the-pivot left right) (cond [(= right left) right] [else (cond [(< (vector-ref V right) the-pivot) right] [else (find-new-right V the-pivot left (sub1 right))])])) Figure: Rearranging a vector fragment into two partitions

Figure  contains the complete definition of partition, partition-aux, and find-new-right; the function swap is defined in figure . The definition of the search function uses an unusual structural recursion based on subclasses of natural numbers whose limits are parameters of the function. Because the search functions are based on a rarely used design recipe, it is best to design them separately. Still, they are useful only in the context of partition, which means that they should be integrated into its definition when their design is completed.

Exercise 43.1.4

Complete the definition of find-new-left. The two definitions have the same structure; develop the common abstraction.

Use the definitions of find-new-right and find-new-left to provide a termination argument for partition-aux.

Use the examples to develop tests for partition. Recall that the function computes the proper place for the pivot item and rearranges a fragment of the vector. Formulate the tests as boolean-valued expressions.

When the functions are properly tested, integrate find-new-right and find-new-left into partition and eliminate superfluous parameters.

Finally, test qsort and produce a single function definition for the in-place quick-sort algorithm. Solution

Exercise 43.1.5

Develop the function vector-reverse!. It inverts the contents of a vector; its result is the modified vector.

Hint: Swap items from both ends until there are no more items to swap. Solution

Exercise 43.1.6

Economists, meteorologists, and many others consistently measure various things and obtain time series. All of them need to understand the idea of ``n-item averages'' or ``smoothing.'' Suppose we have weekly prices for some basket of groceries:

Computing the corresponding three-item average time series proceeds as follows:

There are no averages for the end points, which means a series with k items turns into k-2 averages.

Develop the function list-3-average, which computes the 3-item sliding averages of a list of numbers. That is, we represent a series of grocery prices with lists, and list-3-averages consumes a list such as

(list 1.10 1.12 1.08 1.09 1.11)

(list 1.10 329/300 328/300)

Develop the function vector-3-averages, which computes the 3-item sliding averages of a vector of numbers. Since vectors are mutable, this gives us the alternative of producing a new vector or mutating the existing one.

Develop both versions of the function: one that produces a new vector and another one that mutates the vector it is handed.

Warning: This is a difficult exercise. Compare all three versions and the complexity of designing them. Solution

Exercise 43.1.7

All the examples in this section deal with vector fragments, that is, intervals of natural numbers. Processing an interval requires a starting point for an interval, an end point, and, as the definitions of find-new-right and find-new-left show, a direction of traversal. In addition, processing means applying some function to each point in the interval.

Here is a function for processing intervals:

;; for-interval : N (N -> N) (N -> N) (N -> X) -> X
;; to evaluate (action i (vector-ref V i)) for i, (step i), ... 
;; until (end? i) holds (inclusive) 
;; generative recursion: step generates new value, end? detects end 
;; termination is not guaranteed  
(define (for-interval i end? step action) 
  (begin 
    (action i) 
    (cond 
      [(end? i) (action i)] 
      [else (for-interval (step i) end? step action)]))) 

  (for-interval i end? step action)
= (begin (action i) 
         (action (step i)) 
         ... 
         (action (step (step ... (step i) ...)))) 

With for-interval we can develop (some) functions on vectors without the traditional detour through an auxiliary function. Instead, we use for-interval the way we used map for processing each item on a list. Here is a function that adds 1 to each vector field:

;; increment-vec-rl : (vector number) -> void
;; effect: to increment each item in V by 1 
(define (increment-vec-rl V) 
  (for-interval (sub1 (vector-length V)) zero? sub1 
                (lambda (i) 
                  (vector-set! V i (+ (vector-ref V i) 1))))) 

Here is a function with the same visible effect on vectors but a different processing order:

;; increment-vec-lr : (vector number) -> void
;; effect: to increment each item in V by 1 
(define (increment-vec-lr V) 
  (for-interval 0 (lambda (i) (= (sub1 (vector-length V)) i)) add1 
                (lambda (i) 
                  (vector-set! V i (+ (vector-ref V i) 1))))) 

Develop the following functions, using for-interval:

1. rotate-left, which moves all items in vector into the adjacent field to the left, except for the first item, which moves to the last field;
2. insert-i-j, which moves all items between two indices i and j to the right, except for the right-most one, which gets inserted into the i-th field (cmp. figure );
3. vector-reverse!, which swaps the left half of a vector with its right half;
4. find-new-right, that is, an alternative to the definition in figure ;
5. vector-sum!, which computes the sum of the numbers in a vector using set! (Hint: see section ).

Which of these functions can be defined in terms of vec-for-all from exercise ?

Looping Constructs: Many programming languages (must) provide functions like for-interval as built-in constructs, and force programmers to use them for processing vectors. As a result, many more programs than necessary use set! and require complex temporal reasoning. Solution