Lab: Vectors

Assigned
Monday, Nov 5, 2018
Due
Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
Summary
In this laboratory, you will explore various aspects of the Vector data type that Scheme provides as an alternative to lists.

Preparation

a. Add the following procedures and declarations to your definitions pane.

;;; Procedure:
;;;   random-elt
;;; Parameters:
;;;   lst, a non-empty list 
;;; Purpose:
;;;   Unpredictably pick an element of lst.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * val is an element of lst.
;;;   * If lst contains more than one element, it is difficult to predict 
;;;     which element val is.
(define random-elt
  (lambda (lst)
    (list-ref lst (random (length lst)))))

;;; Procedure:
;;;   random-vector-elt
;;; Parameters:
;;;   vec, a non-empty vector
;;; Purpose:
;;;   Unpredictably pick an element of vec.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * val is an element of vec.
;;;   * If vec contains more than one element, it is difficult to predict
;;;     which element val is.
(define random-vector-elt
  (lambda (vec)
    (vector-ref vec (random (vector-length vec)))))

;;; Value:
;;;   word-list
;;; Type:
;;;   list of strings
;;; Contents:
;;;   A sample list of strings, taken from one of the Project Gutenberg
;;;   collection.
(define word-list
  (file->words "/home/rebelsky/Desktop/pg1260.txt"))

;;; Value:
;;;   word-vector
;;; Type:
;;;   vector of strings
;;; Contents:
;;;   A sample vector of strings, taken from one of the Project Gutenberg
;;;   collection.
(define word-vector
  (list->vector word-list))

;;; Procedure:
;;;   random-word
;;; Parameters:
;;;   words, a list or vector of strings
;;; Purpose:
;;;   Randomly select one element from words
;;; Produces:
;;;   word, a string
;;; Preconditions:
;;;   words is not empty
;;; Postconditions:
;;;   * word is an element of words.
;;;   * If words contains more than one element, word is difficult to
;;;     predict
(define random-word
  (lambda (words)
    (if (vector? words)
        (random-vector-elt words)
        (random-elt words))))
    
;;; Procedure:
;;;   random-words
;;; Parameters:
;;;   words, a list or vector of strings
;;;   n, a non-negative integer
;;; Purpose:
;;;   Randomly select n words from words.
;;; Produces:
;;;   some-words, a list of strings
;;; Preconditions:
;;;   words is not empty
;;; Postconditions:
;;;   * All elements of some-words appear in words.
;;;   * (length some-words) = n
;;;   * The elements and order of some-words is difficult to predict.
(define random-words
  (lambda (words n)
    (if (zero? n)
        null
        (cons (random-word words)
              (random-words words (- n 1))))))

;;; Procedure:
;;;   number-vector-increment-at!
;;; Parameters:
;;;   vec, a vector
;;;   index, an integer
;;; Purpose:
;;;   Increment the value at a vector position
;;; Produces:
;;;   [Nothing; called for side effect.]
;;; Preconditions:
;;;   (vector-ref vec index) is a number
;;; Postconditions:
;;;   Let val be (vector-ref vec index) before the procedure call. After the
;;    call (vector-ref vec index) produces val+1.
(define number-vector-increment-at!
  (lambda (vec index)
    (vector-set! vec 
                 index 
                 (increment (vector-ref vec index)))))

Exercises

Exercise 1: Modifying vectors

Suppose we are considering two names for the same vector and want to try to change the first element. Consider the following code. (That is, read it, don’t enter it.)

> (define chinchilla (vector "a" "b" "c" "d"))
> (define dingo chinchilla)
> (define emu (vector-copy chinchilla))
> (vector-set! chinchilla 0 "Z")

a. What do you expect the output of the following commands to be? (That is, think about the answer; don’t just type it in.)

> (vector-ref chinchilla 0)
_____
> (vector-ref dingo 0)
_____
> (vector-ref emu 0)
_____

b. Check your answer experimentally. (You can type the commands now.)

c. What do you expect the results of the following to be?

> (let* ([gibbon (vector "a" "b" "c" "d")]
         [hippo gibbon]
         [ibex (vector-copy gibbon)])
    (vector-set! gibbon 0 "Z")
    (list gibbon hippo ibex))

d. Check your answer experimentally.

e. What do your results of these experiments suggest about vectors in Scheme?

Exercise 2: Selecting random elements

a. Make sure that you can explain the difference between random-elt, random-vector-elt, and random-word.

b. Using random-words and word-list, make a list of ten randomly selected words.

c. Using random-words and word-vector, make a list of ten randomly selected words.

Exercise 3: Exploring efficiency

The reading claims that it is much more efficient to use vectors than lists. Let’s put that claim to the test. We will use the time procedure, which takes as input an expression, evaluates that expression, prints out the time it took to evaluate the expression, and returns that expression.

a. The following expression example is taken from one of our personal computers, which means that the running time could be significantly different than the time you see on another computer. Try that example.

> (define sample (time (random-words word-list 1000)))
cpu time: 1061 real time: 1067 gc time: 11

b. Change the number of elements until you get a cpu time close to one second (somewhere between 750 anad 1250).

c. Verify that sample contains the expected results. For example, you should consider the length and the elements.

d. Run the same command a few more times. Here’s what we see on one of our computers.

> (define sample (time (random-words word-list 1000)))
cpu time: 836 real time: 838 gc time: 0
> (define sample (time (random-words word-list 1000)))
cpu time: 1222 real time: 1222 gc time: 0
> (define sample (time (random-words word-list 1000)))
cpu time: 1182 real time: 1178 gc time: 13
> (define sample (time (random-words word-list 1000)))
cpu time: 1005 real time: 1002 gc time: 12

e. Explain, to the best of your ability, why we see different times.

f. Run the same command using word-vector rather than word-list.

g. Verify that the output is correct. Once again, you should look at the length and contents of the result.

h. Explain any differences in the time for the vector version as compared to the list version.

Exercise 4: Summing vectors

Write a procedure, (vector-sum numbers), that takes one argument, a vector of numbers, and returns the sum of the elements of that vector.

You can use the recursion pattern(s) and number-vector-largest as a starting point. If you do, be sure to cite your sources appropriately.

You may not convert your vector into a list.

Exercise 5: Filling vectors

Write, but do not document, a procedure, my-vector-fill!, that takes two parameters, a vector and a value, and puts that value in every position of the vector.

> (define vec (vector 'a 'b 'c))
> vec
'(a b c)
> (my-vector-fill! vec 0)
> vec
'(0 0 0)
> (my-vector-fill! vec 'a)
> vec
'(a a a)

Some implementations of Scheme come with vector-fill!. You may not use that procedure.

Note: my-vector-fill! is supposed to modify an existing vector. It is pointless to create a new vector.

Note: You may find that you want to do two things for a particular position: fill the value at that position and recur. Remember that when you want to sequence multiple actions if a test succeeds, you should use a cond or when rather than an if.

Exercise 6: Finding elements

Write a procedure, (vector-index vector elt) that looks for elt in vector and returns its index if it appears in the vector and #f otherwise.

> (vector-index (vector 'a 'b 'c) 'b)
1
> (vector-index (vector 'a 'b 'c) 'd)
#f

Exercise 7: Tallying letters

a. Fill in the purpose, product, and postconditions of the following procedure.

;;; Procedure:
;;;   lowercase->number
;;; Parameters:
;;;   letter, a character
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   * letter is a lowercase letter in US English
;;;   * the encoding system numbers letters in the sensible way, with
;;;     each letter's encoding one greater than the encoding of the previous
;;;     letter.  
;;; Postconditions:
;;;
(define lowercase->number
  (let ([a-num (char->integer #\a)])
    (lambda (letter)
      (- (char->integer letter) a-num))))

b. Using lowercase->number and number-vector-increment-at!, write a procedure, (record-letter! tallies letter), that takes as input a vector of integers (representing tallies of the 26 letters) and a letter, and updates the appropriate tally.

> (define tallies (make-vector 26 0))
> tallies
'#(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
> (record-letter! tallies #\c)
> (record-letter! tallies #\z)
> (record-letter! tallies #\c)
> tallies
'#(0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)

c. Finish the following definition of tally-letters-in-string, which takes as input a string and returns a vector that tallies the letters of the string.

(define tally-letters-in-string
  (lambda (str)
    (let ([tallies (make-vector 26 0)])
      (let kernel ([pos (- (string-length str) 1)])
        (when (>= pos 0)
          
         
> (tally-letters-in-string "triskaidekaphobia")
'#(3 1 0 1 1 0 0 1 3 0 2 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0)

For those with extra time

Extra 1: Rotating vectors

Write a procedure, (vector-rotate! vec) that rotates the elements in vec. That is, rotate! puts the initial element of vec at the end, the element at position 1 in position 0, the element at position 2 in position 1, and so on and so forth.

Extra 2: Reversing vectors

a. Write a procedure, (vector-reverse vec), that creates a new vector whose elements appear in the reverse order of the elements in vec.

b. Write a procedure, (vector-reverse! vec), that reverses vec “in place”. That is, instead of producing a new vector, it rearranges the elements within vec.

Extra 3: Rotating vectors, revisited

Write a procedure, (vector-rotate! vec amt), that rotates the values in vec by amt positions. That is, the first amt values in vec move to the end, the value in position amt moves to position 0, the value in position amt+1 moves to position 1, and so on and so forth.

Extra 4: Patterns of recursion

In a number of previous exercises, you wrote procedures that iterated over the vector, changing values as you went. (For example, vector-fill! had this form.) Summarize the form of a procedure that recurs over vectors, setting the value at each position to a new value, much like the recursion patterns given in the reading.