This class will be recorded! Its use is limited to members of the class. Please do not share with others.
Approximate overview
Attend (or watch recording within a day or so) and send a one-paragraph reflection asap afterwards.
Only those activities I list count.
language.rkt.Can we make the long easy-word code faster?
Yes.
You could build a list-of-lists of words.
And then grab the appropriate list from that list-of-lists.
I couldn’t get it done on time. Do I get until Friday at 10:30 p.m. for a token?
Yes.
I need even more time. Can I get until Sunday at 10:30 p.m. for another token?
Yes.
I need even more time. Can I get more than that?
Nope. Turn in what you have on Sunday, with notes to the grader about what works and what does not, and plan to redo it.
No questions.
What are the key aspects of tail recursion?
All the work is done before or in the recursive call, not afterwards.
So the recursive call always stands by itself, it’s never of the form
(f (recursive-call)). That is, if you apply a procedure to the result, it’s not tail recursive.
What about the accumulator?
Accumulators help us write tail-recursive procedures, but are not always necessary.
You can also write tail-recursive procedures without accumulators.
You can also write non-tail-recursive procedures with accumulators.
Is it okay if I write a “normal” recursive procedure first and then think about how to turn it into a tail-recursive procedure?
Certainly.
Can we talk about fold?
I will talk about fold at 9:30 a.m.
Nope
When is SoLA 3?
Next Tuesday.
So soon? I hate the speed of terms.
Me too.
I missed a topic on both SoLA 1 and SoLA 2. Will it be available on SoLA 3?
Yes.
Will there be review sessions?
Yes. Probably Monday night at the normal times.
What are the new LA topics?
That’s a great question. They are posted on the course Web site in the Handouts section.
Wow, those seem to be tilted towards things we’re just learning now.
See note above about terms.
This is week five. Next week is week six. How do we have three SoLAs to go?
SoLA 3 is in week 6.
SoLA 4 is in week 7. (Wednesday)
SoLA 5 is your (optional) final.
Does SoLA 5 have anything new?
Nope. It’s a final chance to make up any missing LAs.
What happens if I get questions wrong on SoLA 5?
Sorry. It’s your last chance.
Remember: You don’t need to complete all LAs.
Do we need to know higher-order recursion for the SoLA?
Nope.
How can I be better, more efficient, etc. in the class?
I recommend keeping a “notebook” of the procedures you’ve written and the patterns you’ve seen.
Schedule your work time around times others are available to help (e.g., evening tutors).
When is the reading on pairs due?
Tomorrow.
Why are you so incompetent at using Gradescope?
42
More seriously, there are enough moving pieces that I miss some. (And I thought I’d fixed that one.)
Continuing from yesterday, same partners.
play-seven-eleven
and not pair-a-dice.Sam will be lecturing. Please ask questions as we go. If Sam doesn’t see a hand, unmute and ask.
;;; (reduce binproc lst) -> any?
;;; binproc : procedure? (of two parameters)
;;; lst : non-empty-list?
;;; Reduce `lst` to a single value by repeatedly applying `binproc`
;;; to neighboring elements.
(define right-reduce
(lambda (binproc lst)
(if (and (not (null? lst)) (null? (cdr lst)))
(car lst)
(binproc (car lst) (right-reduce binproc (cdr lst))))))
(check-equal? (right-reduce + '(1)) 1 "reduce: base-case")
(check-equal? (right-reduce + '(1 2 3)) 6 "reduce: simple case")
(check-equal? (right-reduce string-append '("a" "b" "c" "d"))
"abcd"
"right-reduce: strings")
(check-equal? (right-reduce - '(1 2 3 4 5))
(reduce-right - '(1 2 3 4 5))
"Is this right reduction?")
Note: This is right-associative, like reduce-right. (Sam renamed.)
Why is this right-associative?
Let’s trace.
(right-reduce - '(1 2 3 4))
--> (- 1 (right-reduce '(2 3 4)))
--> (- 1 (- 2 (right-reduce '(3 4))))
--> (- 1 (- 2 (- 3 (right-reduce '(4)))))
--> (- 1 (- 2 (- 3 4)))
The parenthesization suggests that this right recursive.
First stab: Incorrect.
(define reduce-helper
(lambda (binproc lst so-far)
(if (and (not (null? lst)) (null? (cdr lst)))
so-far
(reduce-helper binproc (cdr lst)
(binproc (car lst) so-far)))))
(define reduce
(lambda (binproc lst)
(reduce-helper binproc (cdr lst) (car lst))))
Replacement: Seemingly correct, and in the correct order.
(define reduce-helper
(lambda (binproc lst so-far)
(cond
[(null? lst)
so-far]
[else
(reduce-helper binproc (cdr lst)
(binproc so-far (car lst)))])))
(define left-reduce
(lambda (binproc lst)
(reduce-helper binproc (cdr lst) (car lst))))
This is left-associative.
Let’s trace
(left-reduce - '(1 2 3 4))
--> (reduce-helper - '(2 3 4) 1)
--> (reduce-helper - '(3 4) (- 1 2))
--> (reduce-helper - '(3 4) -1)
--> (reduce-helper - '(4) (- -1 3))
--> (reduce-helper - '(4) -4)
--> (reduce-helper - '() (- -4 4))
--> (reduce-helper - '() -8)
--> -8