SEQUENTIAL vs. RANDOM ACCESS


       SEQUENTIAL ACCESS
(define long-list (list 1 2 3 ... 1000))

(list-ref long-list 900)
 COST:	900 cdr's

(subst 111 900 long-list)
 COST:  900 cdr's
	900 cons

reading nth element O(n) time
writing nth element O(n) time and space


     RANDOM ACCESS

(define long-vec (vector 1 2 3 ... 1000))

(vector-ref long-vec 900)
  COST:  1 unit of time

(vector-set! long-vec 900 111)
  COST:  1 unit of time

reading nth element: O(1) time
writing nth element: O(1) time


   A PICTURE OF A VECTOR VALUE

     < a,   b,   c,   d,   e >    values

       0    1    2    3    4      indexes

    #( a    b    c    d    e )    printed


v: (-> ({0,1,2,3,4}) symbol)
v(0) = a
v(1) =      b
v(2) =           c
v(3) =                d
v(4) =                     e

Def: a (vector T) value is a mapping
 from {0,1,...,n-1} to objects of type T,
where n >= 0


Def: a (vector T) object is
     (make-vector n x)
  or (vector e0 e1 ... en)
where n has type natural
  and x, e0, e1, ..., en have type T


      BASIC PROCEDURES FOR VECTORS

vector : (-> (T ...) (vector T))

make-vector :
  (and (-> (natural T) (vector T))
       (-> (natural) (vector datum)))

vector?: (-> (datum) boolean)

vector-length : (-> ((vector T)) natural)

vector-ref: (-> ((vector T) natural) T)
 ; REQUIRES: the natural number is
 ; less than the length of the vector.

vector-set! : (-> ((vector T) natural T)
                  void)
 ; REQUIRES: the natural number is
 ; less than the length of the vector


(view (vector 1 2 3)) =prints=> #(1 2 3)
(view (vector 3)) =prints=> #(3)
; assume length > 0


(list->vector '()) ==> #()
(list->vector '(a b)) ==> #(a b)
(list->vector (list 0 1 2 3))
     ==> #(0 1 2 3)

list->vector : (-> ((list T)) (vector T))


; compare Program 9.23

(define list->vector
  ; TYPE: (-> ((list T)) (vector T))
  (lambda (ls)
    (let ((vec (make-vector (length ls))))
      (letrec
        ((convert!
            ; TYPE: (-> ((list T) natural)
            ;           void)
           (lambda (ls* i)
	     ; REQUIRES: i <= (length ls),
             ; ls* = (list-tail ls i),
	     ; for all 0 <= j < i:
             ;  (vector-ref vec j)
             ;  = (list-ref ls j)
	     ; MODIFIES: vec
	     ; EFFECT: put ls* into vec
             ; starting at index i
             (if (not (null? ls*))
                 (begin
                   (vector-set! vec i
                     (car ls*))
                   (convert! (cdr ls*)
                            (add1 i)))))))
        (convert! ls 0))
      vec)))


(vector-copy '#(3 4 5)) ==> #(5 8 9)
(eq? v (vector-copy v)) ==> #f
(equal? v (vector-copy v)) ==> #t

vector-copy : (-> ((vector T)) (vector T))

Don't mutate the arguments.
Return a new vector.


Def: an object is mutated if it's value
is changed (e.g., by vector-set!).

Def: an object is new iff
it didn't exist before the call
(so it's not eq? to anything else)


(define vector-copy
  (lambda (v)
    ; ENSURES: result is a new vector
    ; that has the same value as v
    (let ((len (vector-length v)))
      (let ((vec (make-vector len)))
	(letrec
	 ((init!
	   ; TYPE: (-> (natural) void)
	   (lambda (i)
	     ; REQUIRES: i < len
             ; for all 0 <= j < i:
             ;  (vector-ref v j)
             ;  = (vector-ref vec j)
             ; MODIFIES: vec
             ; EFFECT: put the elements
	     ; of v into vec, start at i
	     (if (< i len)
		 (begin
		   (vector-set!
		     vec
		     i
		     (vector-ref v i))
		   (init! (add1 i)))))))
	  (init! 0))
	vec))))


     YOU WRITE

(vec+ '#(3 4 5) '(2 3 4))
   ==> #(5 8 9)

vec+ : (-> ((vector number)
            (vector number))
           (vector number))

Assume the arguments have the same length.
Don't mutate the arguments.
Return a new vector.


   VECTOR-GENERATOR

1. make a new vector
2. fill in as directed
3. return the new vector


((vector-generator (lambda (i) i)) 4)
  ==> #(0 1 2 3)

; want to be able to define...

(define vector-copy
  (lambda (v)
    ((vector-generator
       (lambda (i) (vector-ref v i)))
     (vector-length v))))

(define vec+
  (lambda (v1 v2)
    ((vector-generator
       (lambda (i)
         (+ (vector-ref v1 i)
            (vector-ref v2 i))))
     (vector-length v1))))

vector-generator: 
 (-> ((-> (natural) T))
     (-> (natural) (vector T)))


; - Program 9.21, pg. 283 -

(define vector-generator
  (lambda (gen-proc)
    (lambda (size)
      (let ((vec (make-vector size)))
        (letrec
          ((loop!
            ; TYPE: (-> (natural) void)
	    (lambda (i)
	      ; REQUIRES: i <= size
	      ; and for all 0 <= j < i,
	      ; (vector-ref vec j)
              ;  = (gen-proc j)
	      ; MODIFIES: vec
	      ; EFFECT: initialize indexes
	      ;  i up to size-1
	      (if (< i size)
		  (begin
		    (vector-set!
		      vec
		      i
		      (gen-proc i))
		    (loop! (add1 i)))))))
          (loop! 0))
        vec))))


   YOU WRITE

(list->vector '()) ==> #()
(list->vector '(a b)) ==> #(a b)
(list->vector (list 0 1 2 3))
     ==> #(0 1 2 3)

list->vector : (-> ((list T)) (vector T))

   USING vector-generator (and list-ref)


(vector-map add1 '#(1 2 3))
   ==> #(2 3 4)

; - Program 9.9, pg. 273 -
(define vector-map
  ; TYPE: (-> ((-> (S) T) ((vector S)))
  ;           (vector T))
  (lambda (proc vec)
    ; ENSURES: result is a new vector that
    ; has ith element proc applied to
    ; the ith element of vec
    ((vector-generator
         (lambda (i)
	   (proc (vector-ref vec i))))
     (vector-length vec))))


; - Program 9.11, pg. 274 -

(define vector-apply-elementwise-to-both 
  ; TYPE: (-> ((-> (S T) U))
  ;           (-> ((vector S) (vector T))
  ;               (vector U)))
  (lambda (proc) 
    ; REQUIRES: the lengths of vec1
    ;             and vec2 are equal
    ; ENSURES: result is a new vector that
    ; has ith element proc applied to
    ; the ith element of vec1 and vec2
    (lambda (vec1 vec2) 
      (let ((gen-proc 
              (lambda (i) 
                (proc
		 (vector-ref vec1 i)
		 (vector-ref vec2 i)))))
        ((vector-generator gen-proc)
	 (vector-length vec1))))))

Exercise: use this to define vec+ and vec*
(vec+ (vector 3 4) (vector 5 6)))
        ==> #(8 10)


(vector-sum (vector )) ==> 0
(vector-sum (vector 3 4 5)) ==> 12

vector-sum: (-> ((vector number)) number)


; - Program 9.13, pg. 275 -

(define vector-sum
  (lambda (vec) 
    ; ENSURES: result is the sum of
    ;          the numbers in vec
    (let ((size (vector-length vec)))
      (letrec 
        ((helper
           (lambda (i) 
             (if (= i size) 
                 0 
                 (+ (vector-ref vec i)
		    (helper (add1 i)))))))
        (helper 0)))))

Exercise: write vector-product.
(vector-product (vector )) ==> 1
(vector-product (vector 3 4 5)) ==> 60


; - Program 9.15, pg. 277 -

(define vector-accumulate 
  ;TYPE: (-> ((-> (S T) T) T)
  ;          (-> ((vector S)) (vector T)))
  (lambda (proc seed)
    (lambda (vec)
      (let ((size (vector-length vec)))
        (letrec 
          ((helper
	     ; TYPE: (-> (nat) (vector T))
             (lambda (i)
               (if (= i size)
                   seed 
                   (proc 
		    (vector-ref vec i)
		    (helper (add1 i)))))))
          (helper 0))))))

Exercise: Use this to define vector->list
(vector->list (vector 'next 'please))
   ==> (next please)


 MUTATING VEC-MULT-BY-SCALAR!

> (define v (vector 1 2 3 4))
> (vec-mult-by-scalar! v 3)
> v
#(3 6 9 12)

vec-mult-by-scalar! :
  (-> ((vector number) number) void)


  FUNCTIONAL VEC-MULT-BY-SCALAR

(vec-mult-by-scalar (vector 1 2 3 4) 3)
  ==> #(3 6 9 12)

Return a new vector, do not mutate the arg


(define vec-mult-by-scalar
  ; TYPE: (-> ((vector number) number)
  ;           (vector number))           
  (lambda (v n)
    ; ENSURES: result is a new vector
    ;     with ith element mutiplied by n
    (let ((v-copy (vector-copy v)))
      (vec-mult-by-scalar! v-copy n)
       v-copy)))


 MUTATING VECTOR-REVERSE!

> (define v (vector 1 2 3 4))
> (vector-reverse! v)
> v
#(4 3 2 1)

vector-reverse! : (-> ((vector T)) void)


(define vector-reverse! ;; cf. Prog 9.26
  ;TYPE: (-> ((vector T)) void)
  (lambda (vec)
    ; MODIFIES: vec
    ; EFFECT: reverse vec in place
    (let ((swapv! (swap!-maker vec)))
      (letrec 
        ((switch! ;: (-> (nat nat ) void)
	  (lambda (i j)
	    ; REQUIRES: 0 <= i <= j
	    ; j <= (vector-length vec),
	    ; positions 0..i and j..length
	    ;  have already been swapped
	    (if (< i j)
		(begin
		  (swapv! i j)
		  (switch! (add1 i)
			   (sub1 j)))))))
        (switch! 0
	        (sub1 (vector-length vec))
		)))))
(define swap!-maker ;; Prog 9.27
  ; TYPE: (-> ((vector T))
  ;           (-> (natural natural)
  ;               (vector T)))
  (lambda (vec)
    (lambda (index1 index2)
     (let ((temp (vector-ref vec index1)))
        (vector-update!
          (vector-update! vec index1
		  (vector-ref vec index2))
          index2
          temp)))))


(define vector-reverse
  ; TYPE:(-> ((vector T)) (vector T))
  (lambda (vec)
    (let ((vec-copy (vector-copy vec)))
       (vector-reverse! vec-copy)
       vec-copy)))

; Compare Program 9.24 in the text


; - Program 9.22, pg. 283 -

(define vector-update!
  ; TYPE: (-> ((vector T) natural T)
  ;           (vector T))
  (lambda (vec i c) 
    ; REQUIRES: i is a legal index for vec
    ; MODIFIES: vec
    ; EFFECT: make the ith element of vec
    ;         be c, and return vec
    (vector-set! vec i c) 
    vec))


	A MATRIX	

"Jones, J."  "2117 Plum St."    "412-8421"
"Jones, M."  "1392 First Ave."  "424-7773"
"Jose, M."   "3314 Valley Dr."  "421-0035"
"Joslin, J." "2550 Western"     "412-5531"


    MATRIX VALUES

Def: a (matrix T) value is a mapping
from {(0,0),(0,1),...,(0,n-1),
      (1,0),(1,1),...,(1,n-1),
      ...
      (m-1,0),(m-1,1),...,(m-1,n-1)}
to objects of type T,
where m >= 0 is the number of rows
  and n >= 0 is the number of columns


     MATRIX OBJECTS

Def: a (matrix T) object is
 ((matrix-generator f) m n)
where f has type (-> (natural natural) T),
      m >= 0 is the number of rows
  and n >= 0 is the number of columns.


	BASIC PROCEDURES FOR MATRICES

matrix-generator:
  (-> ((-> (natural natural) T))
      (-> (natural natural)
          (matrix T)))


num-rows: (-> ((matrix T)) natural)
num-cols: (-> ((matrix T)) natural)


matrix-ref: (-> ((matrix T))
                (-> (natural natural) T))
; REQUIRES: the first natural is less than
; the number of columns of the matrix, and
; the second is less than number of rows.


matrix-set! : (-> ((matrix T))
                  (-> (natural natural T)
                      void))
; REQUIRES: the first natural is less than
; the number of columns of the matrix, and
; the second is less than number of rows.


 REPRESENTING MATRICES

Example matrix:
   0   1   2   3
  10  11  12  13
  20  21  22  23


	   ROW MAJOR ORDER

0  1  2  3  10  11  12  13  20  21  22  23


	COLUMN MAJOR ORDER
	
0  10  20  1  11  21  2  12  22  3  13  23


   OUR REPRESENTATION (IDEA IS ROW MAJOR)

(vector
0  1  2  3  10  11  12  13  20  21  22  23
   4)


    INDEX OF i,j IN REP
	
 (row-size)*i+j

; - Program 9.32, pg. 294 -

(define matrix-ref
  (lambda (mat)
    (let ((ncols (num-cols mat)))
      (lambda (i j)
        (vector-ref mat
		    (+ (* i ncols) j))))))


; - Program 9.30, pg. 293 -

(define num-cols
  (lambda (mat)
    (let ((size
	   (sub1 (vector-length mat))))
      (vector-ref mat size))))


; - Program 9.31, pg. 294 -

(define num-rows
  (lambda (mat)
    (let ((size (sub1 (vector-length mat))))
      (/ size (vector-ref mat size)))))


; - Program 9.33, pg. 295 -

(define matrix-generator
  ; TYPE: (-> ((-> (natural natural) T))
  ;           (-> (natural natural)
  ;               (matrix  T)))
  (lambda (gen-proc)
    (lambda (nrows ncols)
      ; ENSURES: result is a matrix of
      ; nrows by ncols whose (i,j)th
      ; element is (gen-proc i j)
      (let ((size (* nrows ncols)))
        (let ((vec-gen-proc
		; TYPE: (-> (natural) void)
                (lambda (k)
		  ; REQUIRES: k <= size
		  ; ENSURES: result is
		  ; the kth element of the
		  ; row vector rep,
		  ; or ncols if k = size
                  (if (< k size)
                      (gen-proc
		       (quotient k ncols) 
		       (remainder k ncols)
		       )
                      ncols))))
          ((vector-generator vec-gen-proc)
           (add1 size)))))))


Exercise: use this to write make-matrix
like make-vector, but curried.
	((make-matrix 0.0) 7 3)


> (define mat ((matrix-generator
		 (lambda (i j)
		   (+ (* 10 i) j)))
	       3 4))
> ((row-of mat) 2)
#(20 21 22 23)

Return a new vector.

(define row-of 
  ; TYPE: (-> ((matrix T))
  ;           (-> (natural) (vector T)))
  (lambda (mat)
    ; ENSURES: (result i) is the ith
    ; row vector of mat,
    ; if 0 <= i < (num-rows mat)
    (let ((mat-ref (matrix-ref mat))
          (number-of-columns
	   (num-cols mat)))
      (lambda (i)
	; REQUIRES: i < (num-rows mat)
        (let ((gen-proc
	       (lambda (j) (mat-ref i j)))
	      )
          ((vector-generator gen-proc)
	   number-of-columns))))))


; - Program 9.39, pg. 300 -

(define matrix-set!
  ; TYPE: (-> ((matrix T))
  ;          (-> (natural natural T) void)
  (lambda (mat)
    (let ((ncols (num-cols mat)))
      (lambda (i j obj)
	; REQUIRES: i < ncols,
	; and j < (num-rows mat)
	; MODIFIES: mat
	; EFFECT: make the (i,j)th
	; element in mat be obj
        (vector-set!
	 mat
	 (+ (* i ncols) j) obj)))))


		SILLY TOY COMPANY

       stl pls rbr               Ames DSM

widget  4   2   2        steel     $8  $7
xylophn 5   2   2        plastic   $4  $5
yack    4   3   1        rubber    $5  $4
zebra   5   5   2


	       Ames     DSM

widgets        $50      $46
xylophn        $58      $53
yack           $49      $47
zebra          $54      $54


(define dot-prod-internal
  ; TYPE: (-> ((matrix number) (matrix number))
  ;           (-> (natural number) number))
  (lambda (mat-a mat-b)
    ; REQUIRES: (num-cols mat-a) = (num-rows mat-b)
    ; ENSURES: (result i j) is the dot product of
    ; the ith row of mat-a and the jth col of mat-b
    (let ((ncols-a (num-cols mat-a))
          (a-ref (matrix-ref mat-a))
          (b-ref (matrix-ref mat-b)))
      (lambda (i j)
	(letrec
	  ((dot-prod ; TYPE: (-> (natural number) number)
	     (lambda (r acc)
	       ; REQUIRES: 0 <= r <= ncols-a
	       ; and acc is the sum of all products of
	       ; the form a[i,r']*b[r',j] for all 0 <= r' < r.
	       ; ENSURES: result is dot product of
	       ; the ith row of mat-a and the jth col of mat-b
	       (if (= r ncols-a)
		   acc
		   (dot-prod (add1 r) 
		     (+ acc (* (a-ref i r) 
			       (b-ref r j))))))))
	  (dot-prod 0 0))))))

(define matrix-product
  ; TYPE: (-> ((matrix number) (matrix number))
  ;           (matrix number))
  (lambda (mat-a mat-b)
    ; REQUIRES: (num-cols mat-a) = (num-rows mat-b)
    ; ENSURES: result is the product of mat-a and mat-b,
    ; i.e., a (num-rows mat-a) by (num-cols mat-b) matrix
    ; whose (i,j)th element is teh dot-product of the ith row of a
    ; and the jth column of b
    (let ((ncols-a (num-cols mat-a))
	  (dot-prod (dot-prod-internal mat-a mat-b)))
      (if (not (= ncols-a (num-rows mat-b)))
          (error "matrix-product:"
		 "The matrices are not compatible.")
	  ((matrix-generator dot-prod) 
	   (num-rows mat-a) (num-cols mat-b))))))

; imperative version, compare program 9.38
(define matrix-product-imp
  ; TYPE: (-> ((matrix number) (matrix number))
  ;           (matrix number))
  (lambda (mat-a mat-b)
    ; REQUIRES: (num-cols mat-a) = (num-rows mat-b)
    ; ENSURES: result is the product of mat-a and mat-b,
    ; i.e., a (num-rows mat-a) by (num-cols mat-b) matrix
    ; whose (i,j)th element is teh dot-product of the ith row of a
    ; and the jth column of b
    (let ((nrows-a (num-rows mat-a))  ; NOTE: different than above!!!
	  (ncols-b (num-cols mat-b))) ; ditto
      (if (not (= (num-cols mat-a) (num-rows mat-b)))
          (error "matrix-product:"
		 "The matrices are not compatible.")
          (let ((mat ((make-matrix 0.0) (num-rows mat-a) (num-cols mat-b)))
		(dot-prod (dot-product-internal mat-a mat-b)))
	    (let ((mat-set! (matrix-set! mat)))
	      (letrec
		((each-row! ; TYPE: (-> (natural) void)
		   (lambda (i)
		     ; REQUIRES: i <= nrows-a
		     ; MODIFIES: mat
		     ; EFFECT: set each element in the ith row of mat to
		     ; the dot-product of the ith row of mat-a and the
		     ; appropriate column of mat-b
		     (letrec
		       ((each-col! ; TYPE: (-> (natural) void)
			  (lambda (j)
			    ; REQUIRES: j <= ncols-b
			    ; EFFECT: set the (i,j)th element of mat to
			    ; the dot-product of the ith row of mat-a and the
			    ; jth column of mat-b
			    (if (< j ncols-b)
				(begin
				  (mat-set! i j (dot-prod i j))
				  (each-col! (add1 j)))))))
		       (if (< i nrows-a)
			    (begin
			      (each-col! 0)
			      (each-row! (add1 i))))))))
		(each-row! 0)
		mat)))))))