Comp 210 Lab 13: More state, including vectors

Vectors, Searching in vectors, Imperative programming

Welcome to the last lab of the semester!

Vectors

Review: Vectors are another abstraction for collections of data. Like a structure, each element of a vector is named, in this case with a number. I.e., they are named 0,1,2,3,... in order. Vectors can be of any length, although you cannot change the length of a particular vector. Some important functions are the following:

(vector v₀ ... v_n-1) creates a vector of length n of the given elements.
(build-vector n f) creates a vector of length n of elements ((f 0) ... (f (sub1 n)))
(make-vector n v) creates a vector of length n, of n instances of v. It is essentially a special case of build-vector.
(vector-length vec) returns the length of the given vector.
(vector-ref vec n) returns the n^th element of the vector.
(vector-set! vec n v) changes the n^th element of the vector to be the given element.

Remember that vector elements are indexed starting with 0, not 1! That means you should never use code like

   (vector-ref vec (vector-length vec))

because there is no such element in the vector.

To do: Write a function that given a vector, returns a new vector of the same length of the squares of the numbers in the original vector. For the curious... Try to find two or more completely different ways to do this.

Searching in vectors

At first glance, it seems like we cannot use a recursive template for vectors because vectors are not defined recursively. So, how do we approach writing interesting functions on vectors? When using vectors, you usually use the template for natural numbers, i.e., the index into the vector. A good set of examples of this is provided by the idea of searching a vector for a particular element.

Actually, we have two natural choices of what to recur on:

an index of the next item to look at or
the number of items to look at.

These are essentially the same thing, but differ by 1 since vectors are 0-indexed. Confusing the two often leads to "off-by-1 errors".

Searching downwards

To do as a group: Finish and test the following program to search a vector. Note that the helper function follows the natural number recursive template.

     ;; vec-search-down? : (any -> boolean) (vectorof any) -> boolean
     ;; Purpose: Returns whether any element of the vector meets the given
     ;;          predicate.
     ;; Examples:
     ;;   (vec-search-down? number? (vector true false)   = false
     ;;   (vec-search-down? number? (vector true 3 false) = true
     ;;   (vec-search-down? number? (vector)              = false
     (define (vec-search-down? pred? a-vec)
        (local [;; search : natnum -> boolean
                ;; Purpose: Returns whether any element 0..num_elts-1 of a-vec
                ;;          meets predicate pred?.
                (define (search num_elts)
                   (cond
                      [(zero? num_elts)
                       ...]
                      [else
                       ...(search (sub1 num_elts))...]))]
           (search ...)))

Solution.

For the curious... Searching upwards

Sometimes we prefer to count upwards instead of downwards. For example, when searching a vector, we could want to return the lowest-indexed element matching our predicate. This doesn't follow our natural number template -- we want to define a number template that counts in the opposite order, so that we recur in the opposite order.

To do: Define the integers up to some n.
To do: Develop the program vec-search-up? which behaves the same way as vec-search-down?, except that it searches in the opposite order. Be careful with the termination condition.

We could follow the natural number template. As we count down, we want to access larger indices, so we need a simple formula to convert from the number we have (counting down) to the index. To do: Develop this version of vec-search-up?.

Both solutions.

Binary search

When searching sorted data, we can use the orderedness of the data to our advantage. We would like the following:

     ;; vec-search-binary? : number (vectorof number) -> boolean
     ;; Purpose: Returns whether any element of the vector is the given
     ;;          number.  Assumes the vector elements are sorted in
     ;;          ascending order.
     ;; Examples:
     ;;   (vec-search-binary? 4 (vector 0 2 3 4 5 8 10 11 15 20 40)) = true

We'll adapt our previous in-class idea of binary search. As a reminder, we started with a bounded range of numbers and guessed if the middle one was the desired one. If not, we knew how to reduce the range by half, and then continue. We can do exactly the same thing now, where the bounded range represents the vector indices we need to consider. We repeatedly look at data elements somewhere in the middle, and thus this algorithm is naturally suited for vectors, since vectors have constant-time access to arbitrary elements.

To do: Develop vec-search-binary? : number (vectorof number) -> boolean, which behaves as just described. You will need a helper function to keep track of the bounded range. A solution.

Imperative Programming

This course has dealt primarily with a style of programming known as functional programming, or to also include the previous couple weeks, mostly-functional programming. Another style is imperative programming, which focuses primarily on side-effects (e.g., set! and set-struct-field!), rather than passing arguments.

Let's get a hint at the relation between these two styles of programming. In particular, let's see an example of how recursion and looping are related.

Labbies: Point out the corresponding syntactic pieces in the following examples.

We start with a simple structurally recursive program:

     (define (sum-list alon)
        (cond [(empty? alon) 0]
              [(cons? alon)  (+ (first alon) (sum-list (rest alon)))]))

We can then obtain the accumulator version:

     (define (sum-list alon)
        (local [(define (sum-list-acc the-lon accum)
                   (cond [(empty? the-lon) accum]
                         [(cons? the-lon)  (sum-list-acc (rest the-lon)
                                                         (+ (first the-lon)
                                                            accum))]))]
           (sum-list-acc alon 0)))

As you've seen, sometimes this step is difficult. Remember that this version adds up the numbers in the oppositive order. Thus, part of the reason it was relatively easy to obtain this version is that addition is associative.

We can rewrite this to avoid passing arguments in the helper function and, instead, change only local variables. (This step is interesting mainly for pedagogical reasons.) This is a straightforward syntactic translation:

     (define (sum-list alon)
        (local [(define accum 0)
                (define the-lon alon)
                (define (sum-list!)
                   (cond [(empty? the-lon) accum]
                         [(cons? the-lon)  (begin
                                              (set! accum
                                                    (+ (first the-lon) accum))
                                              (set! the-lon
                                                    (rest the-lon))
                                              (sum-list!))]))]
           (sum-list!)))

Q: Does the order of the two set!s matter? Why or why not?

Lastly, we can rewrite this using one of Scheme's several looping constructs. This is another straightforward syntactic translation:
```
     (define (sum-list alon)
        (local [(define accum 0)]
           (begin
              (loop-until alon
                          empty?
                          rest
                          (lambda (the-lon)
                             (set! accum (+ (first the-lon) accum))))
              accum)))
     
```
loop-until takes four arguments: a starting value to loop on, a test for what value(s) to stop on, a function to get the next loop value from the current one, and a function to evaluate on each loop iteration. Q: What's the contract for loop-until?

Most programming languages have a construct similar to this, except with a test for what value(s) to continue looping (i.e., the opposite of what's used here). It is typically called a while loop.

This process is insufficient for all programs, but it shows that recursion and iteration are closely related. They are both useful tools.

Which version is best?

The first is stylistically best, because it is the most easily understood. Also, it is much easier to make mistakes in the versions with set!.
They are all essentially equally efficient -- they each recur one per list element. However, they may differ by constant factors. What these constant factors are and which version is fastest both depend completely on how DrScheme is implemented.

To do: Write imperative versions of

the vector searching functions
factorial
foldl
for the curious... foldr (This is harder than foldl, because it is harder to obtain an accumulator-style version of it.)
for the curious... the sum of elements in a tree

You may use the above steps if you find them helpful, or just skip to the solution.