Approximate overview
Token Events
Reminder to self: Try to get FJ&I moved to 8pm.
Other good things
Do we have class next Wednesday? I want to go home for Thanksgiving.
Yes, but if you want to do the lab on your own, I’ll understand.
Do we really have only four more labs this semester?
That sounds about right.
For part 3, what do you want as output?
Minimally
That Web page has 4 image(s) without alt text
That Web page has 1 href(s) with only one word
That Web page has 0 neighboring href(s)
Better: SXML structure
Even better:
(image-errors (@ (number 4))
(img "pres.png")
(img "serp.png")
(img "samr.png")
(img "whatever.png"))
Or
That Web page has 4 image(s) without alt text. You should fix
pres.png, sepr.png, samr.png, whatever.png
What do we want for an href?
In HTML
<a href=...">TEXT</a>. We want the text.
In SGML
(a (@ (href ..)) TEXT). We still want the text.
Did you remember why you originally had no lab for today?
Yes.
match is one of those things the CS faculty have differing viewpoints on.
Let’s look at a typical direct list-recursive procedure, such as append.
What’s our base case?
Example for thought
(append '(a b c) '(d e f))
-->(??? ??? (append '(b c) '(d e f)))
-->(??? (car '(a b c)) '(b c d e f))
-->(??? 'a '(b c d e f))
(define append
(lambda (lst1 lst2)
(if (null? lst1)
lst2
(cons (car lst1) (append (cdr lst1) lst2)))))
Example, once the procedure is written
(append '(a b c) '(d e f))
--> (cons 'a (append '(b c) '(d e f)))
--> (cons 'a (cons 'b (append '(c) '(d e f))))
--> (cons 'a (cons 'b (cons 'c (append '() '(d e f)))))
--> (cons 'a (cons 'b (cons 'c '(d e f))))
--> (cons 'a (cons 'b '(c d e f)))
--> (cons 'a '(b c d e f))
--> '(a b c d e f))
In thinking about recursive procedures over structures, we often choose our cases based on the form of the structure.
The designers of Racket decided to give us the opportunity to write our recursive (or other) procedures in a way that reflects this way of thinking.
(define append
(lambda (lst1 lst2)
(if (null? lst1)
lst2
(let ([first (car lst1)]
[rest (cdr lst1)])
(cons first (append rest lst2)))))
To express this structurally, using match, we write
(define append
(lambda (lst1 lst2)
(match lst1
['()
lst2]
[(cons first rest)
(cons first (append rest lst2))])))
Some people find this easier to think about and/or to read.
(define xml-process
(lambda (xml)
(match xml
[(cons 'em rest)
...]
[(cons '@ rest)
...]
[(cons first rest)
...]
[anything-else
...])))
A piece of text matches anything.
Nice things about match:
append and list-ref are expensive (in that they require a lot
of work to cdr through the list). Try to avoid calling them
again and again and again in a recursive procedure.
Direct recursion is your friend! (Or it’s supposed to be your
friend.) Here’s how I expected you to think about index-of-by.
;;; (index-of-by lst pred?) -> integer? or crash!
;;; lst : list?
;;; pred? : unary predicate
;;; Find the first index of a value for which pred? holds.
(define index-of-by
(lambda (lst pred?)
(cond
[(null? lst)
#f]
[(pred? (car lst))
0]
[else
(??? (index-of-by (cdr lst) pred?))])))
Suppose:
(index-of-by '(2 4 1 4) odd?)`
--> (??? (index-of-by '(4 1 4) odd?))
--> (??? 1)
Oh! We just need to add 1.
(define index-of-by
(lambda (lst pred?)
(cond
[(null? lst)
#f]
[(pred? (car lst))
0]
[else
(+ 1 (index-of-by (cdr lst) pred?))])))
Let’s trace!
(index-of-by '(2 4 1 4) odd?)`
--> (+ 1 (index-of-by '(4 1 4) odd?))
--> (+ 1 (+ 1 (index-of-by '(1 4) odd?)))
--> (+ 1 (+ 1 0))
--> (+ 1 1)
--> 2
Let's fix that
Let’s trace something else!
(index-of-by '(2) odd?)
--> (+ 1 (index-of-by '() odd?))
--> (+ 1 #f)
--> BOOM!
(define index-of-by
(lambda (lst pred?)
(cond
[(null? lst)
#f]
[(pred? (car lst))
0]
[else
(let ([index-in-tail (index-of-by (cdr lst) pred?)])
(and index-in-tail
(+1 index-in-tail)))])))
Remember (if TEST CONSEQUENT #f) -> (and TEST CONSEQUENT)
Can we write this with match? Not easily.
One of the morals: Sometimes naming the result of your recursive call can be helpful.
Another moral: Yay! More basic procedures you know how to write.
Key ideas of tail recursion:
Or
Also
There are (at least) two ways people approach writing tail-recursive procedures.
How do we start turning a direct recursive procedure into a tail-recursive procedure?
Our recursive procedure:
(define recursive
(lambda (params)
(if (base-case-test params)
(default-value params)
(combine params (recursive (simplify params))))))
Our tail recursive procedure:
(define tail-recursive
(lambda (params)
(letrec ([helper
(lambda (so-far remaining)
(if (base-case-test remaining)
so-far
(helper (combine so-far remaining) (simplify remaining))))])
(helper (default-value params) params))))
Why do we need let, let*, and letrec?
It turns out that the implementation of each is subtly different, and it’s much more complicated to implement
letrec.
How do I write procedures with a variable number of parameters?
Sam would prefer that you not do so. But …
(lambda params ...), puts all of the parameters in a single list.
(lambda (p1 p2 . p3) ...), requires at least two parameters, puts all of the remaining parameters into p3.
(define count-parameters
(lambda params
(length params)))
(define tsil
(lambda params
params))
(define optional-third-parameter
(lambda (a b . c)
(if (null? c)
"There is no third parameter"
c)))
Goal: Find the value with the highest absolute value in a list of real numbers.
(define furthest-from-zero
(lambda (lst)
(displayln (list 'furthest-from-zero lst))
(if (null? (cdr lst))
(car lst)
(if (> (abs (car lst))
(abs (furthest-from-zero (cdr lst))))
(car lst)
(furthest-from-zero (cdr lst))))))
Some “sad” output
> (furthest-from-zero '(4 -3 1))
(furthest-from-zero (4 -3 1))
(furthest-from-zero (-3 1))
(furthest-from-zero (1))
4
> (furthest-from-zero '(-5 4 -3 1))
(furthest-from-zero (-5 4 -3 1))
(furthest-from-zero (4 -3 1))
(furthest-from-zero (-3 1))
(furthest-from-zero (1))
-5
> (furthest-from-zero '(7 -5 4 -3 1))
(furthest-from-zero (7 -5 4 -3 1))
(furthest-from-zero (-5 4 -3 1))
(furthest-from-zero (4 -3 1))
(furthest-from-zero (-3 1))
(furthest-from-zero (1))
7
> (furthest-from-zero '(1 -3 4 -5 7))
(furthest-from-zero (1 -3 4 -5 7))
(furthest-from-zero (-3 4 -5 7))
(furthest-from-zero (4 -5 7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (4 -5 7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (-3 4 -5 7))
(furthest-from-zero (4 -5 7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (4 -5 7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
(furthest-from-zero (-5 7))
(furthest-from-zero (7))
(furthest-from-zero (7))
7
>
Yes.