This class will be recorded! Its use is limited to members of the class. Please do not share with others.
Approximate overview
stuff [~10 min]
Events
I’m not sure if all of these links are correct. Let me know if any are not.
When will the autograder be ready?
I have no idea. I’ll start writing it at 6pm.
What does “hard-coding” mean?
In the “random card” procedure, you could write something like
(vector-ref card-values (random 13))or(vector-ref card-values (random (vector-length card-values)))or(random-vector-element card-values).
It’s much better to allow the code to adapt to different inputs or changes in variables. “(random 13) does not allow it to adapt.
So don’t use particular numbers if you can avoid it.
Can I use a for loop?
You can
for-each, which may be close enough to what you are thinking of.
How do I write more elegant code for the insanely long code that follows?
(define easy-word?
(let ([words-starting-with-a (words-starting-with #\a easy-words)]
[words-starting-with-b (words-starting-with #\b easy-words)]
...)
(lambda (word)
(cond
[(word-starts-with? #\a word)
(member word words-starting-with-a)]
))))
Use a vector (or list or hash) of length 26 (that holds the 26 lists) for the big let.
You can probably build it using map.
In the body, figure out the index in the vector (or list or hash) and just look there.
This will take you from ~60 lines to about 12.
Some of you seem inclined to use append to build lists in your tail
recursive procedures. Using append likely obviates any benefit
you may get from tail recursion. Remember: append is expensive.
(define insert-between-helper
(lambda (val lst so-far)
(cond
[(null? lst)
so-far]
[(null? (cdr lst))
(append so-far lst)]
[else
(insert-between-helper val
(cdr lst)
(append so-far
(list val)
(list (car lst))))])))
(define insert-between-tail
(lambda (val lst)
(insert-between-helper val lst null)))
(define insert-between
(lambda (val lst)
(if (or (null? lst)
(null? (cdr lst)))
lst
(cons (car lst)
(cons val
(insert-between val (cdr lst)))))))
;;; (time-ib ib size) -> (void)
;;; ib : one of the insert-between? procedures
;;; size : positive-integer
;;; Quickly time how long a version of insert-between takes on
;;; a list of the given size.
(define time-ib
(lambda (ib size)
(let* ([tmp (make-list size 'b)]
[result (time (ib 'a tmp))])
(void))))
> (time-ib insert-between-original 1000)
cpu time: 1 real time: 1 gc time: 0
> (time-ib insert-between-original 10000)
cpu time: 35 real time: 64 gc time: 18
> (time-ib insert-between-original 100000)
cpu time: 2946 real time: 3340 gc time: 2772
> (time-ib insert-between-tail 1000)
cpu time: 48 real time: 53 gc time: 31
> (time-ib insert-between-tail 10000)
cpu time: 3254 real time: 3861 gc time: 1894
Moral: Don’t use append for tail recursion! It’s too expensive.
Why? append is an expensive procedure. Let’s write it.
; We will recurse over lst1
; Use direct recursion
(define my-append
(lambda (lst1 lst2)
(if (null? lst1)
lst2
(cons (car lst1) (my-append (cdr lst1) lst2)))))
Using this repeatedly takes 1 + 2 + 3 + 4 + … + (length of the longest list) steps.
For example, if the list has length 100
1 + 2 + 3 + …. + 100 = 101 * 50 = 5050
Here’s a sample solution to vector-tally.
(define vector-tally
(lambda (vec pred?)
(letrec ([helper (lambda (vec pred? so-far pos)
(cond [(equal? (vector-length vec) pos)
so-far]
[(equal? #t (pred? (vector-ref vec pos)))
(+ 1 (helper vec pred? so-far (+ 1 pos)))]
[(equal? #t (not (pred? (vector-ref vec pos))))
(helper vec pred? so-far (+ 1 pos))]))])
(helper vec pred? 0 0))))
There are at least five things that bother me about this otherwise-correct code. Can you tell what they are? (And yes, I realize that good style is not at the top of your mind when you do SoLAs.)
First, we should reindent
(define vector-tally
(lambda (vec pred?)
(letrec ([helper (lambda (vec pred? so-far pos)
(cond [(equal? (vector-length vec) pos)
so-far]
[(equal? #t (pred? (vector-ref vec pos)))
(+ 1 (helper vec pred? so-far (+ 1 pos)))]
[(equal? #t (not (pred? (vector-ref vec pos))))
(helper vec pred? so-far (+ 1 pos))]))])
(helper vec pred? 0 0))))
Second, we might want to factor out some of the repeated 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))]
(cond
[(equal? #t good?)
(+ 1 (helper vec pred? so-far (+ 1 pos)))]
[(equal? #t (not good?))
(helper vec pred? so-far (+ 1 pos))]))))])
(helper vec pred? 0 0))))
Third, we might want to deal with the equal #t (embrace the Zen of Booleans)
(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))))
For tomorrow: What else could we fix?
;;; (la2let n) -> string?
;;; n : integer?
;;; Convert a count of LAs to a letter grade.
(define la2let
(lambda (n)
(cond [(< n 21)
"Other"]
[(and (>= n 21)
(< n 24))
"C"]
[(and (>= n 24)
(< n 27))
"B"]
[(and (>= n 27)
(<= n 28))
"A"])))
;;; (hash-increment! hash key) -> void?
;;; hash : hash?
;;; key : string?
(define hash-increment!
(lambda (hash grade)
(hash-set! hash grade (increment (hash-ref hash grade 0)))))
;;; (record-grades! grades list-of-la-counts) -> (void?)
;;; grades : hash?
;;; list-of-la-counts : listof integer?
;;; See problem for specs.
(define record-grades!
(lambda (grades list-of-la-counts)
(let [(letter-grades (map (section la2let <>) list-of-la-counts))]
(map (section hash-increment! grades <>) letter-grades))))