Lecture 35: Vectors at Work

###
Lecture 35: Vectors at Work

1. to compute with vectors, everything has to be represented with numbers
   making mistakes with numbers is far easier than making mistakes with first/rest
2. scanning vectors

   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!

                      (define status (build-vector FLOORS (lambda (i) #f)))

       A N/FLOORS is either
         - FLOORS
         - (sub1 n) where n is an N/FLOORS
       A N is either
         - 0
         - (add1 n) where n is an N
       ;; find-true-up : N/FLOORS -> N or #f
       ;; Purpose : determine the first index i:
       ;;   cf <= i < FLOORS 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-down : 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 (cond
       	    ((vector-ref status (sub1 cf)) (sub1 cf))
       	    (else (find-true-down (sub1 cf)))))))

   The vector is not an argument of the functions. The index into the vector is.

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

3. adding numbers in a vector : (vec num) -> num

   Example:

       (define a-vec (build-vector 4 (lambda (i) i)))
       (define L 4)

       A N/L is either
         - L
         - (sub1 n) where n is an N/L
       A N is either
         - 0
         - (add1 n) where n is an N
       ;; add-vec : N^L -> num
       ;; Purpose : add numbers in a-vec between i and L-1
       (define (add-vec i)
         (cond
           ((= i L) 0)
           (else (+ (vector-ref a-vec i)
       	     (add-vec (add1 i))))))
       ;; add-vec : N -> num
       ;; Purpose : add numbers in a-vec between i-1 and 0
       (define (add-vec i)
         (cond
           ((= i 0) 0)
           (else (+ (vector-ref a-vec (sub1 i))
       	     (add-vec (sub1 i))))))
   (add-vec 0) | (add-vec (vector-length a-vec))

   Now wrap everything in a local and abstract over a-vec.

4. abstraction for vectors

   many programming languages define (some variant of) the following abstraction:

       ;; for-i= : N (N -> boolean) (N -> N) (N -> void) -> void
       (define (for-i= i stop-now? step action)
         (cond
           ((stop-now? i) (void))
           (else (begin
       	    (action i)
       	    (for-i= (step i) stop-now? step action)))))

       (define (add-up a-vec)
         (local ((define sum 0))
           (begin
             (for-i= 0 (lambda (x) (= x L)) add1
       	      (lambda (i)
       		(set! sum (+ sum (vector-ref a-vec i)))))
             sum)))
       (define (add-down a-vec)
         (local ((define sum 0))
           (begin
             (for-i= (sub1 (vector-length a-vec)) zero? sub1
       	      (lambda (i)
       		(set! sum (+ sum (vector-ref a-vec i)))))
             sum)))
   (add-up a-vec) | (add-down a-vec)

Matthias Felleisen | This page was generated on Tue Apr 20 22:47:41 CDT 1999.