CSC151.01 2015S, Review Session Week 11: Vectors and Beyond
===========================================================

_Overview_

* You ask questions, I attempt to answer.
* We talk about the forthcoming quiz.

Your Questions
--------------

_How do I make recursion happen with a cond?_

> Yesterday, we attempted to write `(list-select lst pred?)`, which builds
  a new list that contains all elements of `lst` for which `pred?` holds.
  For example,

        > (list-select (list "Sticky" "frogs" 4 "national" 1) number?)
        '(4 1)
        > (list-select (list "Sticky" "frogs" 4 "national" 1) string?)
        '("Sticky" "frogs" "national")

> In solving this problem, we might consider three cases: No elements,
  the predicate holds for the car of the list, everything else.

> No elements -> null

> Predicate holds -> cons the element onto recursive call

> Everything else -> Throw away the first element and use the recursive call

        (define list-select 
          (lambda (lst pred?)
            (letrec ([kernel (lambda (remaining)
                               (cond
                                 [(null? remaining)
                                  null]
                                 [(pred? (car remaining))
                                  (cons (car remaining) (kernel (cdr remaining)))]
                                 [else
                                  (kernel (cdr remaining))]))])
              (kernel lst))))

        (define list-select
          (lambda (lst pred?)
            (let kernel ([remaining lst])
              (cond
                [(null? remaining)
                 null]
                [(pred? (car remaining))
                 (cons (car remaining) (kernel (cdr remaining)))]
                [else
                 (kernel (cdr remaining))]))))

        (define list-select
          (lambda (lst pred?)
            (let kernel ([remaining lst]
                         [selected null])
              (cond
                [(null? remaining)
                 selected]
                [(pred? (car remaining))
                 (kernel (cdr remaining) (cons (car remaining) selected))]
                [else
                 (kernel (cdr remaining) selected)]))))

> The last version has a bug.  We get the values in reverse order.

_Can we talk about vectors and how you do recursion over vectors?_

> Really bad ASCII art for the list '(a b c)

        +--+--+      +--+--+      +--+--+
        |  | *-----> |  | *-----> |  | /|
        +|-+--+      +-|+--+      +-|+--+
         v             v            v
         a             b            c

> Really bad ASCII art for the vector '#(a b c)

        +--+--+--+--+
        |3 |  |  |  |
        +--+|-+|-+|-+
            v  v  v
            a  b  c

> The thing at the beginning tells us how many elements are in the vector,
  so we don't need to put a null at the end.

> The vector uses less memory!  

> It's really easy to find the ith element in a vector.  Just offset
  i*(box-width) from the start of the vector.

> So we can get any element quickly.

> Custom: You can change the values in a vector, you shouldn't change
  the values in a cons cell/pair.  (DrRacket won't let you do the latter.)
  For a collection of information that might change, a vector is often
  better.

> If it's an indexed collection of things that can change, what operations
  do we need?  

    * Create a new vector.  `(make-vector len val)`, `(vector val1 val2 val3 .. valn)`.  (We are specifying the number of elements, so DrRacket knows how much space to allocate and can put the "how many elements" number at the beginning.)
    * Extract a value from a vector.  `(vector-ref vec pos)`. 
    * Change a value in the vector.  `(vector-set! vec pos newval)`.

_How do we "recurse" over vectors?  (E.g., change very value, use every
 value, etc.)_

> We recurse over positions using techniques of numeric recursion.
  Either count up from 0 to length-1, or count down from length-1 to 0.

> Example: Double every element in a vector.  Counting down.

        (define vector-double!
          (lambda (vec)
            (let kernel ([pos (- (vector-length vec) 1)])
              (display (list 'kernel pos vec)) (newline) ; Watch
              (when (>= pos 0)
                (vector-set! vec pos (* 2 (vector-ref vec pos)))
                (kernel (- pos 1))))))

> Pattern: Do something to every element in a vector, counting down

        (define vector-_____!
          (lambda (vec)
            (let kernel ([pos (- (vector-length vec) 1)])
              (when (>= pos 0)
                _______________________ ; e.g., (vector-set vec pos ...)
                (kernel (- pos 1))))))

> Example: Half every element in a vector, counting up

        (define vector-whatever!
          (lambda (vec)
            (let kernel ([pos 0])
              (when (< pos (vector-length vec))
                (vector-set! vec pos (* 1/2 (vector-ref vec pos)))
                (kernel (+ pos 1))))))

> Sam doesn't like to recompute vector lengths (mostly it's a bad habit
  to recompute list lengths)

        (define vector-whatever!
          (lambda (vec)
            (let ([len (vector-length vec)])
              (let kernel ([pos 0])
                (when (< pos len)
                  (vector-set! vec pos (* 1/2 (vector-ref vec pos)))
                  (kernel (+ pos 1)))))))

> We don't always use `when`

> Example: vector-sum, counting up

        (define vector-sum
          (lambda (vec)
            (let ([len (vector-length vec)])
              (let kernel ([pos 0]
                           [partial-sum 0])
                (if (< pos len)
                    (kernel (+ pos 1)
                            (+ partial-sum (vector-ref vec pos)))]
                    partial-sum)))))

About the Quiz
--------------

Main topics:

* Vectors.
* Randomness.

Likely quiz questions:

* Interpret _this code_.
* Finish writing _this code_ that is supposed to accomplish _this task_.
* Find the bugs in _this code_ that is supposed to accomplish _this task_.