Lecture 34: Vectors 1

###
Lecture 34: Vectors 1

1. mathematical vectors

   a mathematical vector is a compound mathematical datum that keeps track of many things -- posn for many different dimensions, not just 2: space, time, temperature, ... one of our colleagues works with 20-dim spaces

        ( a1 ... aN )

   they are called N-tuples

   [okay, this is not the most general def but it does for here]

   there are two key operations on vectors in mathematics:

        V1 + V2 :: addition of two vectors
        s  * V  :: multiplication of a vector with a scalar

   in our simple example, vector addition means pointwise addition of two N-tuples and the multiplication of the scalar with every item in the vector

        (a1 ... aN) + (b1 ... bN) = (a1+b1 ... aN + bN)
        s * (a1 ... aN)           = (s * a1... a * aN)

2. Scheme vectors:

        build-vector : N (N -> X) -> (vector X)
        vector-ref   : (vector X) N -> X

   Task: define scalar* and vector+

       ;; scalar* : num (vector num) -> (vector num)
       ;; Purpose: scalar multipl for vectors
       (define (scalar* s vec)
         (build-vector (vector-length vec) (lambda (i) (* s (vector-ref vec i)))))

       ;; vector+ : (vector num) (vector num) -> (vector num)
       ;; Purpose: vector addition (pointwise)
       (define (vector+ vec1 vec2)
         (build-vector (vector-length vec1)
       		(lambda (i) (+ (vector-ref vec1 i) (vector-ref vec2 i)))))

   Now define scalar-product:

       ;; scalar-product : (vector num) (vector num) -> num
       ;; Purpose: scalar product for vectors
       ;; Example: (a1 .. aN> sp*  = a1 * b1 + ... + aN * bN
       (define (scalar-product vec1 vec2)
         (foldl + 0
       	 (build-list (vector-length vec1)
       		     (lambda (i)
       		       (* (vector-length vec1) (vector-length vec2))))))

       ;; norm : (vector num) -> num
       ;; Purpose: compute the size (length) of a vector
       (define (norm vec)
         (sqrt (scalar-product vec vec)))

3. Aren't Scheme vectors just lists?

       (define build-vector build-list)
       (define vector-length length)

       ;; list-ref : (listof X) N -> X
       ;; Purpose: determine the a-nn-th item on a-list, start counting with 0
       (define (list-ref a-list a-nn)
         (cond
           ((and (cons? a-list)  (= a-nn 0)) (first a-list))
           ((and (empty? a-list) (= a-nn 0)) (error ...))
           ((and (empty? a-list) (> a-nn 0)) (error ...))
           (else (list-ref (rest a-list) (sub1 a-nn)))))

       (define vector-ref list-ref)

   No. Access to items is constant time:

   list | vector | structures
   --- | --- | ---
   build-list : N (N -> X) -> (listof X) | build-vector : N (N -> X) -> (listof X) | (define-structure foo (ab cd ef))
   ... creates arbitrarily large values | ... creates arbitrarily large values | ... creates values from three components
       Access:
       (list-ref (list 'a 'b 'c) 2)
       Access:
       (vector-ref (list 'a 'b 'c) 2)
       Access:
       (foo-ef (make-foo 2 3 4))
   ... requires a-nn recursions | ... is instantaneous | ... is instantaneous

   In short, a vector combines the properties of a list (combines arbitrarily many values into one) and a structure (gives instantaneous access to the constituent values)

4. When to use lists? When to use vectors?

   if a program potentially inspects "all" constituents, use list

   if a program inspects individual constituents at "random", use vector

   Example: the elevator program (picture) -- hardware needs to record the status of floors and the controller needs to sweep over it to find the proper one

   - When someone presses a button on floor n, status vector's n-th component should change:

         vector-set! : (vector X) N X -> void

         (vector-set! status n PRESSED)

     Once it is served, the elevator should record that too:

         (vector-set! status n SERVED)

   - When elevator is served, we need to start scanning the status vector from the "middle" -- i.e. the floor where it currently is

   Here are the basic sketches on our canvas:

       ;; FLOORS : num
       (define FLOORS 10)

       ;; status : (vec boolean)
       (define status (build-vector FLOORS (lambda (floor) #f)))

       ;; controller : num { 'up 'down } -> num
       (define (controller cf dir)
         (cond
           ((eq? dir 'up)   (up-controller cf))
           ((eq? dir 'down) (down-controller cf))))

       -------------------------------------------------------------------------
                                                  cf
       -------------------------------------------------------------------------
       upwards: find #t, starting from            | ==>
       downwards: find #f, starting from       <==|

       (define (up-controller cf)
         (local ((define upwards-demand (find-true-up cf)))
           (cond
             (upwards-demand upwards-demand)
             ((find-true-down cf) (find-true-down cf))
             (else cf))))

       (define (down-controller cf)
         (local ((define downwards-demand (find-true-down cf)))
           (cond
             (downwards-demand downwards-demand)
             ((find-true-up cf) (find-true-up cf))
             (else cf))))

   If something is arbitrarily large, we need an inductive data definition. What is inductive about `(build-vector n 'x)` ? The natural number! We need to work with variations on natural numbers!

       ;; find-true-up : N -> N or #f
       ;; Purpose : determine the first index i:
       ;;   FLOORS > i >= cf where status is #t
       ;;   otherwise produce #f
       (define (find-true-up cf)
         (cond
           ((= cf FLOORS) #f)
           (else (cond
       	    ((vector-ref status cf) cf)
       	    (else (find-true-up (add1 cf)))))))
       ;; find-true-up : N -> N or #f
       ;; Purpose : determine the first index i:
       ;;   cf > i >= 0 where status is #t
       ;;   otherwise produce #f
       (define (find-true-down cf)
         (cond
           ((= cf 0) #f)
           (else
            (local ((define new (sub1 cf)))
              (cond
       	 ((vector-ref status new) new)
       	 (else (find-true-down new)))))))

       #| Tests: |#

       ;; press button on 0th floor
       (vector-set! status 0 #t)
       (= (controller 3 'up) 0)
       (= (controller 3 'down) 0)

       ;; press button on 6th floor
       (vector-set! status 6 #t)
       (= (controller 3 'up) 6)
       (= (controller 3 'down) 0)

Matthias Felleisen | This page was generated on Mon Apr 19 09:00:37 CDT 1999.