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) and send a one-paragraph reflection.
mp4.rkt.mp5.rkt.Yesterday, we wrote the following procedure.
(define my-filter
(lambda (pred? lst)
(cond
[(null? lst)
null]
[(pred? (car lst))
(cons (car lst) (my-filter pred? (cdr lst)))]
[else
(my-filter pred? (cdr lst))])))
Can we use tail recursion?
Of course.
Time for random recitation.
What are the basic ideas of tail recursion?
so-far.What are the basic ideas of higher-order recursion?
;;; (remove val lst) -> list?
;;; val : any?
;;; lst : list?
;;; Remove all copies of val from lst
(define remover
(lambda (val lst)
(cond
[(null? lst)
null]
[(not (equal? (car lst) val))
(cons (car lst) (remover val (cdr lst)))]
[else
(remover val (cdr lst))])))
(check-equal? (remover "um" '("um" "the" "list" "of" "examples" "um"))
'("the" "list" "of" "examples")
"Edge case: thing to remove is at both ends")
(check-equal? (remover 7 '(3 4 5 7 7))
'(3 4 5)
"Multiple copies at end")
(check-equal? (remover 5 '(0 5 5 0))
'(0 0)
"Bon, Jame Bon")
(check-equal? (remover 5 '())
'()
"Empty list")
(check-equal? (remover 5 '(1 2 3))
'(1 2 3)
"Not present")
Can we write the body of remover as a call to filter?
(define remover
(lambda (val lst)
(let ([pred? (lambda (x) (not (equal? x val)))])
(my-filter pred? lst))))
Important lesson: Once we’ve written my-filter, we may never
again have to write that pattern of recursion; we can just call
my-filter.
If we think of a better way to write my-filter, such as a tail-recursive version, we get the gain everywhere, not just in one procedure.
The point here is that if DrRacket did not include filter, we could
write it ourselves using simpler things (if, car, cdr). You are empowered.
(define my-filter-helper
(lambda (pred? lst so-far)
(cond
[(null? lst)
(reverse so-far)]
[(pred? (car lst))
(my-filter-helper pred? (cdr lst) (cons (car lst) so-far))]
[else
(my-filter-helper pred? (cdr lst) so-far)])))
(define my-filter
(lambda (pred? lst)
(my-filter-helper pred? lst null)))
Why not use letrec?
I find it better to start by writing a separate helper.
Note: Tail recursion tends to reverse lists, so we need to reverse them again.
What counts as a non-trivial procedure?
Not nearly identical to the earlier problems.
If I spend one token do I get until Friday night?
Yes
Are there evening tutors on Friday night?
No
Will Sam be online Friday night?
Probably not
Please explain the following
; A non-empty list whose first element is 2
> (find-match '(join 2 x)
'(((1 2) 3) (2 3) (2 1) (1 4) 5))
'(2)
'(join 2 x) match the whole value? No.'(join 2 x) match somewhere in the car of the whole value? ‘((1 2) 3)
'(join 2 x) match somewhere in the cdr of the whole value? ‘((2 3) (2 1) (1 4) 5)There’s an implicit list that starts with 2.
We build
'(1 2)implicitly as(cons 1 (cons 2 null))
If the pattern is
(list 1 2 3 x), it should return the first list/sublist/subsublist/etc, that has the form'(1 2 3 x)(four element list that starts with 1 2 3).
It always returns the first/leftmost matching thing, if there is one.
It sounds like there’s recursion involved here.
Yes.
Does that mean find-match should do its own recursion?
Yes. Recursion is awesome!
Do we have to return all instances?
No, just the first.
But if you wanted to write another procedure that returns all matches, the graders would enjoy reading that.
If we wanted to return all matches, what should we do?
Your goal should be to return a list of matches, rather than a match or #f. If there are not matches, return the empty list.
Append all the matches in the car to all the matches in the cdr. Add the whole thing on the front if it matches.
For MP4, should we use all the given tests and, if so, can we keep them as is?
You should use the given tests.
No, they don’t have to be a test suite. Sam likes “Include them and cross your fingers.”
I find it hard to jump to tail recursion. Is that okay? Tips for jumping straight to tail recursion?
Practice.
Can we talk about fold?
Not today.
Why does random with no params work?
It’s designed that way, even though the meaning is slighty different. Some folks like to make procedures work in multiple ways depending on how many or what type of parameters they are given.
Why does (random 0) not work?
Random comes up with a number between 0 (inclusive) and parameter (exclusive).
There no numbers between 0 and 0 that are not 0.
Are we doing randomness tomorrow?
Yes.
Reminder: I recommend the following strategy for quizzes
If you have not already done so …
The lab will continue tomorrow!
Please only do the A side today. (That makes it easier if we have a different set of students here tomorrow.)