COMP 210 Lab 12: More State, Including Vectors

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))

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. E.g., to search for an element find-element in vector v, we would write a helper function (search find-element v i), which recurs on number i.

Searching downwards

Note the few small differences in your solutions. A common mistake is to produce code that looks partly like each of those solutions. Depending on the details, that typically results in not accessing the first or last element, or trying to access an element before the first or after the last. These are all known as "off-by-1 errors".

Searching upwards

Binary search

When searching sorted data, we can use the orderedness of the data to our advantage. We can adapt our previous 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.

     ; 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
     ;   (vec-search-binary? 3 (vector))                            = false

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-structure-component!), 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. Some of the corresponding syntactic pieces are highlighted in color.

1. We start with a simple structurally recursive program:

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

2. 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.

3. We can rewrite this to avoid passing arguments in the helper function and, instead, change only local variables. This step is similar to the assembly-language code that a compiler would produce. 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!)))
        

   Question

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

4. 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.

   Question

   What must the contract for loop-until be?

   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.