Named Let and Vectors

Summary

In this lab you will learn about two topics, the named let and also the vector data structure type. You'll notice how the named let is a great way to write helper functions, and especially useful with vectors.

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 in maroon 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))
> vec
#3(a b c)

> (vector-set! vec 2 #f)
> 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

Using Vectors

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!

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

Exercise 2

This one's a little 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. Let me know if you come up with a better solution. :) 

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