COMP 210 Lab 12: More State, Including Vectors

Vector basics, Searching in vectors, Imperative programming

Vector Basics

A list can contain as many items as you like, but you can only access the first element directly. In contrast, we'll introduce a new structure -- vectors -- where you can access (say) the 17th element directly, but the structure contains exactly a pre-determined fixed number of items.

(define colors (vector 'teal 'ecru 'lilac 'maroon 'red))

(vector-ref colors 3)
(vector-ref colors 0)
(vector-ref colors 5) ; ERROR -- indices must be in [0,5).

(vector-length colors)

(vector-set! colors 3 'macaroni)
(vector-ref colors 3)

In addition to creating vectors via vector, there is also a function build-vector, which creates a vector where the i'th location is initialized to a function of i: (build-vector 5 sqr) (build-vector 5 (lambda (i) (* 2 i)))

In comments, we'll often write "v[i]", as a shorthand for "(vector-ref v i)".

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 when created, although you cannot change the length of a particular vector.

When to use a list:
- when you don't know in advance, now many data you will have;
- when you tend to process all the data together (rather than just the 17th item).
When to use a vector:
- when the data is inherently indexed (e.g. "the measurement taken on day #17");
- when you routinely want to access an item by its index, and not process the rest of your data;
- when you know in advance how many data you will have.

Example: When msn.net was first set up, people could sign up for accounts. When they got their one-millionth customer, their code broke -- the site was down for three days, and a million customers couldn't log on to the net. Presumably they'd used vectors, when a list would be more appropriate. (They wanted the random-access of a vector, but didn't know the number of elements in advance. At the very least, their code for adding a new customer should have had refused the millionth customer, rather than crashing the system for everybody!)

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.

We won't worry about all of the following, but for your reference, here is a summary of several built-in vector functions:

(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 (counting from zero).
(vector-set! vec n v) changes the n^th element of the vector to be the given element (counting from zero).









Vector exercises



 Develop a function vector-square! that,
     given a vector of numbers, destructively
     changes the vector to contain the squares of the old elements.
          (define v (vector 1 3 5 2))
     (vector-square! v)
     v                              evaluates to (vector 1 9 25 4)
     
          (define (vector-square! v)
        (vector-square-help! v (vector-length v)))

     ;; vector-square-help!: vector, natnum --> ...
     ;; Destructively wquare the first n elements of v.
     ;;
     (define (vector-square-help! v n)
        ...)
     
     (The function can either return some dummy value like 'woohoo,
     or (slightly more helpfully) the same vector that was passed in. )
 Develop a function that, given a vector of numbers, returns a
     new vector of the same length containing the squares of
     the numbers in the original vector.
     (Use build-vector.)
          (define v (vector 1 3 5 2))
     (define w (vector-square v))
     v                              returns (vector 1 3 5 2)
     w                              returns (vector 1 9 25 4)
     



Modify your previous program so that instead of following the NatNum
template down to 0, instead it starts at 0 and increases.








Note, there are really two different things here:

 given i, do a task involving i: (vector-set! v i (sqr (vector-ref v i)))

 rig the function to do this task, with i being 0, 1, 2, ..., n-1.





Hey, let's separate these two things explicitly.
The latter part is looping from 0 up to (not including) n.
Examples:



To square each element of the vector nums,
we'll be able to write:
(loop-for 0
          (vector-length nums) 
          (lambda (i) (vector-set! nums i (sqr (vector-ref nums i)))))



We saw in lab last time printf,
where (printf "x is ~v." x) will (as a side-effect)
print the value of x to the screen.
With our loop construct, one could write:
(loop-for 1
          20
          (lambda (i) (printf "The square root of ~v is ~v.~n" i (sqrt i))))




What is the general form for this looping function, loop-for?
;; loop-for: num, num, (num-->(void)) --> 'done
;;
(define (loop-for start-val stop-val body!)
  ...)


Write the general function loop-for, 
where you explicitly return 'done if the start-val
exceeds the stop-val; otherwise you do two things: call body!,
then recursively call loop-for.
(Note: this is an abstraction similar to foldr for natural-numbers:
it allows us to seperate the code for an individual task
from the iterative process of calling that task on 0, 1, 2, ...)


Imperative Programming

To do:
Using the above loop-for,
write a function which sums all the numbers in a vector.


Hint:
define a variable sum-so-far to be 0 initially,
and then as you loop, set! that variable.






To Think about: what if we frequently wanted to do something 
             with every other number in a range?

Should we modify the task (body!), 
or modify the control-logic in charge
of applying body! to the right values?
Both ways work; the latter is better, since it separates the
individual task from the looping.




Loops without mutation


Do we need to use mutation, to make use of a for-loop?
No, we actually have been doing stuff all along which didn't:
Recall:
(triangle-number 3)  = 1 + 2 + 3 = 6
(countdown 3) = (list 3 2 1 'blastoff)



(define (triangle-number n)
  (loop-for-acc 1 (add1 n)
                0    ; The initial sum-so-far (accumulator).
                (lambda (i so-far) (+ i so-far))))   ; A body which creates new accum.

(define (countdown n)
  (loop-for-acc 0 n
                '(blastoff)  ; Initial accumulator value.
                (lambda (i so-far) (cons (add1 i) so-far))))


Exercise: write a version of loop-for-acc
which separates the work that you're doing
from of doing that work with 0, then with 1, ..., then with i-2, then with i-1.
(define (loop-for-acc strt stop init body )
  ..)


Let's see how it actually works: A hand-evaluation quickly shows:
  (countdown 3) 
= (loop-for-acc 0 3  '(blastoff)        (lambda (i so-far) (cons (add1 i) so-far)))
= (loop-for-acc 1 3  '(1 blastoff)      (lambda (i so-far) (cons (add1 i) so-far)))
= (loop-for-acc 2 3  '(2 1 blastoff)    (lambda (i so-far) (cons (add1 i) so-far)))
= (loop-for-acc 3 3  '(3 2 1 blastoff)  (lambda (i so-far) (cons (add1 i) so-far)))
= '(3 2 1 blastoff)