;; Sid Stamm
;; C211 lab number 9: Vectors and Named Let
;; 10-30-2003

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Named Let
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; It seems a bit odd to use internal defines to define
;; helper functions inside a procedure, doesn't it?  Most of
;; the other scheme expressions you've learned evaluate to
;; some value, but the internal definitions evaluate to
;; a void.  There's got to be a simpler way....

;; If it's non recursive, you can use let:
(define func1
  (lambda (x)
    (define help (lambda (a) (* a a)))
    (help x)))

(define func1
  (lambda (x)
    (let ([help (lambda (a) (* a a))])
      (help x))))

;; They're both the same.  For all practical purposes,
;; though, we need recursive helpers.  So wouldn't it be
;; nice if let allowed us to define recursive helpers?
;; Well, there's one that is made for helpers, we'll see
;; that.  First, let's look at a way to do what we
;; want (no void-returning) with a definition:

(define count-down
  (lambda (n)
    (define help
      (lambda (x acc)
	(if (zero? x)
	    acc
	    (help (sub1 x) (cons x acc)))))
    (reverse (help n '()))))

;; We need the helper, because we have to reverse the
;; result: do something after the recursion.
;; let's look at something new:

;(let name ([a1 v1] ...)
;  body)

;; This creates a new procedure called "name" and taking
;; parameters (a1 ...).  It starts it out with initial
;; values of (v1 ...) and then allows you to recur inside.
;; It's the same as:

;(begin
;  (define name (lambda (a1 ...) body))
;  (name b1 ...))

;; So we can make a helper!
(define count-down
  (lambda (n)
    (reverse (let help ([x n] [acc '()])
	       (if (zero? x)
		   acc
		   (help (sub1 x) (cons x acc)))))))

;; This creates a helper and starts it with x=n and acc='()
;; Then it does its thang and returns the result. Look what
;; happens if we just evaluate it alone starting x = 12.

(count-down 12)
;(12 11 10 9 8 7 6 5 4 3 2 1)

(let help ([x 12] [acc '()])
  (if (zero? x)
      acc
      (help (sub1 x) (cons x acc))))
;(1 2 3 4 5 6 7 8 9 10 11 12)

;; it does everything but reverse!
;; This is known as a named let.  Remember print-differences?
;; Check it out with named let.  (Note that nothing between
;; the dividers changes!

(define print-differences
  (lambda (ls1 ls2)
    (define help
      (lambda (a b count)
;;----------------------------------------;;	
	(if (null? a)
	    (printf "differences: ~s~%" count)
	    (if (equal? (car a) (car b))
		(help (cdr a) (cdr b) count)
		(begin
		  (printf "~s and ~s differ~%" (car a) (car b))
		  (help (cdr a) (cdr b) (add1 count)))))
;;----------------------------------------;;
	))
    (help ls1 ls2 0)))

;; with named let...
(define print-differences
  (lambda (ls1 ls2)
    (let help ([a ls1] [b ls2] [count 0])
;;----------------------------------------;;	
      (if (null? a)
	  (printf "differences: ~s~%" count)
	  (if (equal? (car a) (car b))
	      (help (cdr a) (cdr b) count)
	      (begin
		(printf "~s and ~s differ~%" (car a) (car b))
		(help (cdr a) (cdr b) (add1 count)))))
;;----------------------------------------;;	
      )))


;; So named let is useful.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; VECTORS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Vectors are another way of storing data.  Like a list they
;; store a series of elements, but unlike a list the size
;; of a vector cannot change.  What does this give us?
;; Instead of taking k loop iterations to find the kth
;; element of the list, you can access any element of a
;; vector immediately.

;; Vectors are created much like records. (Remember
;; define-record?)  The first thing the vector record stores
;; is the length of itself.  When you see it printed in the
;; repl window, it's the first number following the #.
;; Then the vector stores the items (displayed as a list).
;; i.e:
;#n(a1 a2 ...)

;; There are two ways to make a vector:

;(make-vector n v)
;; This method creates a vector n-elements long that each
;; contain the value v.  v is an optional argument, if it is
;; not provided make-vector puts 0 in all the spots:

(make-vector 5)
;#5(0)

(make-vector 5 'x)
;#5(x)

;(vector a b ...)
;; This method creates a vector containing all the elements
;; after "vector" in the expression:

(vector 1 2 3)
;#3(1 2 3)

(vector)
;#0()

;; THERE IS NO CAR OR CDR OR CONS for VECTORS! Instead you
;; have these tools:  vector-ref, vector-set!, vector-length

;; vector-ref:
;;--------------------
;; Takes a vector and a position and returns
;; whatever is at that location in the vector:

(vector-ref (vector 0 1 2 3) 2)
;2

;; NOTE: the position argument is zero-based, so the first
;; location of the vector is element 0.

;; vector-set!:
;;--------------------
;; Careful with this thing, it mutates the vector you pass
;; in as the parameter.  Basically what it does is change
;; the value of one of the elements in a vector:
(define vec (vector 'a 'b 'c))
(write vec)
;#3(a b c)

(vector-set! vec 2 #f)
(display vec)
;#3(a b #f)

;; Unless you want to rebuild the entire vector, this is
;; the only way to change a single element.

;; vector-length:
;;--------------------
;; This returns (you guessed it!) the length of a vector

(vector-length (vector 1 2 3 'x 'y 'z))
;6

;; Here's an example procedure that loops through a vector
;; and returns a new vector of the same length but the
;; elements are all whatever is passed in as "sym"
(define vector-fake
  (lambda (v sym)
    (let ([len (vector-length v)])
      (make-vector len sym))))

(vector-fake (vector 1 2 3) 'x)
;#3(x)

;; Here's a little different one, this one loops through
;; the vector provided and makes a new vector with each
;; element as a pair of what was originally there.  If the
;; initial vector had an x in position zero, the new one
;; would have a (x x) in position zero.  Since there is no
;; way to construct the vector on the fly, we have to make
;; it, then set all its values.

(define vector-dubble
  (lambda (v)
    (let ([len (vector-length v)])
      (let ([newv (make-vector len)])
	(let loop ([i 0])
	  (if (= i len)
	      newv
	      (begin (vector-set! newv i (list (vector-ref v i)
					       (vector-ref v i)))
		     (loop (add1 i)))))))))

(vector-dubble (vector 'a 1 #f))
;#3((a a) (1 1) (#f #f))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Exercises
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Yay!  It's time for your weekly mind games!

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; EX 1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; [ PART A ]
;;--------------------
;; Define a vector called labs that contains the names of each
;; of the labs 1-7 that you have done before.  You can find
;; them at http://www.cs.indiana.edu/~sstamm/c211/
;; Each entry in that vector should be a string.  The first
;; lab should be in location 0 of the vector and should be
;; called "Define" (this is not on the web site, the rest are).

;; [ PART B ]
;;--------------------
;; Define another vector lab-grades that contains the grades
;; you got on each of your labs as written in your lab book.
;; If you missed a lab or don't have a grade marked in the
;; book enter a 'Z for that entry.  An example would look
;; like:

> lab-grades
#7(s s s u s u z)

;; In this case, I got an S on labs 1 2 3 & 5, a U on labs
;; 4 and 6 and I missed lab 7.

;; [ PART C ]
;;--------------------
;; Write a procedure match-grades that takes two parameters
;; v-labs and v-grades and returns a vector that contains
;; dotted pairs in each entry.  The dotted pairs should be
;; (<name of lab> . <grade on lab>) such that the first
;; element comes from v-labs and the second from v-grades
;; in their respective locations.  Your desired result
;; will be a single vector containing 7 dotted pairs.
;; Use named let and loop through the vectors.

;; Example (I omitted the names of labs 2-7 since you
;; have to figure those out):
> (match-grades labs lab-grades)
#7(("Define" . s)
   (<lab 2 name> . s)
   (<lab 3 name> . s)
   (<lab 4 name> . u)
   (<lab 5 name> . s)
   (<lab 6 name> . u)
   (<lab 7 name> . z))


;; SOLUTIONS
;;--------------------
;;A
(define labs (vector "Define"
		     "Acme Sports Drinks"
		     "Combine"
		     "Cons & Recursion"
		     "Recursion & More"
		     "Using Let!"
		     "Data & Trees"))

;;B (example solution)
(define lab-grades (vector 'S 'S 'S 'U 'S 'U 'Z))

;;C
(define match-grades
  (lambda (v-labs v-grades)
    (let ([len (vector-length v-labs)])
      (let ([v (make-vector len)])
	(let loop ([i 0])
	  (if (= i len)
	      v
	      (begin (vector-set! v i (cons (vector-ref v-labs i)
					    (vector-ref v-grades i)))
		     (loop (add1 i)))))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; EX 2 (harder)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; [ PART A ]
;;--------------------
;; Write a procedure report-grades that takes the result
;; vector from part C on ex 1, and prints the numbers of
;; S's, U's and Z's in the following format:

S count: 4
U count: 2
Z count: 1

;; In this case, I had 3 labs with an S, 2 with U and 2
;; with Z.

;; [ PART B ]
;;--------------------
;; Modify report-grades so that it internally uses
;; match-grades and takes two parameters v-labs and
;; v-grades.  Change it more so it prints out a list
;; of the labs (string names) after the count.

;; EXAMPLE:
;; I have once again omitted the lab names in the example:

S count: 4 (<lab 5 name> <lab 3 name> <lab 2 name> "Define")
U count: 2 (<lab 6 name> <lab 4 name>)
Z count: 1 (<lab 7 name>)


;; SOLUTIONS
;;--------------------
;; A
(define report-grades
  (lambda (v-matched)
    (let ([len (vector-length v-matched)])
      (let ([v-result (make-vector len 0)])
	(let loop ([i 0])
	  (if (= i len)
	      (begin ;;display results
		(printf "S count: ~s~%" (vector-ref v-result 0))
		(printf "U count: ~s~%" (vector-ref v-result 1))
		(printf "Z count: ~s~%" (vector-ref v-result 2)))
	      (begin
		(case (cdr (vector-ref v-matched i))
		  [(s) (vector-set! v-result 0
				    (add1 (vector-ref v-result 0)))]
		  [(u) (vector-set! v-result 1
				    (add1 (vector-ref v-result 1)))]
		  [(z) (vector-set! v-result 2
				    (add1 (vector-ref v-result 2)))])
		(loop (add1 i)))))))))
						  
		   
;; B
;; For this solution, I am building a vector that contains
;; tuples.  Position 0 represents s, it contains a dotted
;; pair that contains the number and then a list of lab names.
(define report-grades
  (lambda (v-labs v-grades)
    (let ([len (vector-length v-labs)]
	  [v-matched (match-grades v-labs v-grades)])
      (let ([v-result (make-vector len '(0 . ()))])
	(let loop ([i 0])
	  (if (= i len)
	      (begin ;;display results
		(let ([l-s (vector-ref v-result 0)]
		      [l-u (vector-ref v-result 1)]
		      [l-z (vector-ref v-result 2)])
		  (printf "S count: ~s ~s~%" (car l-s) (cdr l-s))
		  (printf "U count: ~s ~s~%" (car l-u) (cdr l-u))
		  (printf "Z count: ~s ~s~%" (car l-z) (cdr l-z))))
	      (begin
		(let ([l-s (vector-ref v-result 0)]
		      [l-u (vector-ref v-result 1)]
		      [l-z (vector-ref v-result 2)])
		  (case (cdr (vector-ref v-matched i))
		    [(s) (vector-set! v-result 0
				      (cons (add1 (car l-s))
					    (cons (vector-ref v-labs i)
						  (cdr l-s))))]
		    [(u) (vector-set! v-result 1
				      (cons (add1 (car l-u))
					    (cons (vector-ref v-labs i)
						  (cdr l-u))))]
		    [(z) (vector-set! v-result 2
				      (cons (add1 (car l-z))
					    (cons (vector-ref v-labs i)
						  (cdr l-z))))]))
		(loop (add1 i)))))))))