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.