This class will be recorded! Its use is limited to members of the class. Please do not share with others.
Approximate overview
Events
I’m not sure if all of these links are correct. Let me know if any are not.
Is there a formula for 1 + 2 + … + n? Yes. But rather than teach you the formula, I’m going to teach you to derive it.
Step 1: Name the result.
x = 1 + 2 + ... + n-2 + n-1 + n
Step 2: Rely on your intuition (or at least my intuition)
Reverse and add
Step 3: Algebra!
x = 1 + 2 + 3 ... + n-2 + n-1 + n
x = n + n-1 + n-2 ... + 3 + 2 + 1
--------------------------------------
2x = (1+n) + (1+n) + (1+n) + ... + (1+n)
2x = n(1+n)
x = n(n+1)/2
Here’s the vector-tally procedure we were (re-)writing in yesterday’s class.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(let* ([val (vector-ref vec pos)]
[good? (pred? val)])
(cond
[good?
(+ 1 (helper vec pred? so-far (+ 1 pos)))]
[(not good?)
(helper vec pred? so-far (+ 1 pos))]))))])
(helper vec pred? 0 0))))
Bad Sam! Where are the tests?
(test-equal? "vector-tally/a: empty vector"
(vector-tally (vector) odd?)
0)
(test-equal? "vector-tally/b: pred holds for first and some other values"
(vector-tally (vector 1 2 3 4 5 6) odd?)
3)
(test-equal? "vector-tally/c: pred holds for last and some other values"
(vector-tally (vector 2 3 4 5 6 7 8) even?)
4)
(test-equal? "vector-tally/d : singleton vector, pred holds"
(vector-tally (vector "hello") string?)
1)
(test-equal? "vector-tally/e: singleton vector, pred does not hold"
(vector-tally (vector 2) string?)
0)
(test-equal? "vector-tally/f: pred holds for all values"
(vector-tally (vector 11 10 9 1 2 3 4 5) (section > <> 0))
8)
(test-equal? "vector-tally/f: pred holds for no values"
(vector-tally (vector 11 10 9 1 2 3 4 5) (section < <> 0))
0)
(test-equal? "vector-tally/g: string->number as predicate"
(vector-tally (vector "one" "2" "three" "45" "6.7" "eight")
string->number)
3)
What did we fix before?
let to factor out common code.What else can/should we fix? Do any of the principles we used apply here? What else?
Use an if instead of a cond
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(let* ([val (vector-ref vec pos)]
[good? (pred? val)])
(if good?
(+ 1 (helper vec pred? so-far (+ 1 pos)))
(helper vec pred? so-far (+ 1 pos))))))])
(helper vec pred? 0 0))))
Factor out common code.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(let* ([val (vector-ref vec pos)]
[good? (pred? val)]
[tally-rest (helper vec pred? so-far (+ 1 pos))])
(if good?
(+ 1 tally-rest)
tally-rest))))])
(helper vec pred? 0 0))))
Elminate one of the pointless let bindings
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(let* ([val (vector-ref vec pos)]
[tally-rest (helper vec pred? so-far (+ 1 pos))])
(if (pred? val)
(+ 1 tally-rest)
tally-rest))))])
(helper vec pred? 0 0))))
Either eliminate the so-far (which never changes) or actually make this tail recusive.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(let* ([val (vector-ref vec pos)])
(if (pred? val)
(helper vec pred? (+ 1 so-far) (+ 1 pos))
(helper vec pred? so-far (+ 1 pos))))))])
(helper vec pred? 0 0))))
Oh! val is only used once.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(if (pred? (vector-ref vec pos))
(helper vec pred? (+ 1 so-far) (+ 1 pos))
(helper vec pred? so-far (+ 1 pos)))))])
(helper vec pred? 0 0))))
Now we have a cond
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (vec pred? so-far pos)
(cond
[(equal? (vector-length vec) pos)
so-far]
[(pred? (vector-ref vec pos))
(helper vec pred? (+ 1 so-far) (+ 1 pos))]
[else
(helper vec pred? so-far (+ 1 pos))]))])
(helper vec pred? 0 0))))
Two of the helper’s parameters don’t change. Elimiante them.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (so-far pos)
(cond
[(equal? (vector-length vec) pos)
so-far]
[(pred? (vector-ref vec pos))
(helper (+ 1 so-far) (+ 1 pos))]
[else
(helper so-far (+ 1 pos))]))])
(helper 0 0))))
Optional: Go back to an if to help eliminate repeated code.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper
(lambda (so-far pos)
(if (equal? (vector-length vec) pos)
so-far
(helper (+ (if (pred? (vector-ref vec pos))
1
0)
so-far)
(+ 1 pos))))])
(helper 0 0))))
That may not be better.
Where do we stand on tokens?
Everyone has infinitely many tokens.
When I’m working vectors and hashes and other mutable stuff, I often
need two consequent or two alternates. How do I do that with if?
Don’t do it with
if. Usecondorwhendepending on the situation.
E.g.,
(define vector-swap!
(lambda (vec i j)
(when (and (integer? i)
(integer? j)
(>= i 0)
(>= j 0)
(< i (vector-length vec))
(< j (vector-length vec)))
(first-thing!)
(second-thing!))))
YOu can’t write
(if TEST
(first!) (second!)
(alternate!))