-----------------------------------------
Tutorial notes #7 for 4/2 or 4/3/2007
TA: Stephen McCamant
Email: smcc@mit.edu
Location: 36-113A or 36-115
http://people.csail.mit.edu/smcc/6.001-sp07/
-----------------------------------------
Project 2 hand-back
Median grade (my section): 94/100
Median guessing game score: 52.5/100
-----------------------------------------
Project 2 common issues
- Don't re-implement standard functions:
even?, expt, foldr, reverse
- Use the question sequence as a hint
about what procedures to use, e.g.:
fand, negation in true-but-not-always
- Higher-order functions can be more
elegant if you can avoid the need for
an extra lambda. Examples: negation,
skip-most-recent-n
- guess-last is better than car
- Watch out for ambiguities in the
procedure specifications (questions 5
and 7 were both bad this way)
- For writing questions, be sure to
answer *why*, not just what
- Don't forget to test
- Testing isn't just about running you
code. You also have to be able tell
whether the results were right.
- Question 12 was an example of code
that is hard to test, since it's random
and returns only #t or #f
Common mistake: returning a function
(supplied code was not type-defensive)
Ideas on good ways to test?
1/2 + 1/8 + 1/32 + 1/128 + ... = ?
- If the learning game beat you by more
than a few points, you weren't trying
hard enough (but I didn't deduct
points)
- Question 18 was open-ended, so to get
maximum credit, we were looking for an
answer that was both original and
good.
Not very original: combinations of
existing functions, (lastn infinity)
Common bad idea: randomized functions
If the player is playing 90% #t and
10% #f, what's the best strategy to
have in allfuncs?
- In question 19, using irrational
numbers wasn't actually a very helpful
suggestion, since DrScheme's fractions
only have about 50 bits of
information.
Getting around too-few digits
Don't have to be truly random, just
weird enough to fool the learner
- Redundancies I got tired of seeing:
(if pred X X)
(if pred #t #f)
(if pred #f #t)
(eq? X #t)
(eqv? X #t)
(equal? X #t)
(eq? X #f)
((lambda (n) n) X)
((lambda (a) (X a)) v)
-----------------------------------------
Project 3 suggestions
- We're asking you to write bigger
pieces of code now, so plan ahead
about how to break things up into
procedures.
- Useful procedure: for-each is like
map, but doesn't make a list of the
results.
- Watch out: some of the supplied
accessors are not defensive about
checking tags.
- There are a number of places where
fold-right is useful, if you're
comfortable with it.
-----------------------------------------
Mutation review
(set! variable value)
(set-car! pair value)
(set-cdr! pair value)
set! is a special form that mutates
variable bindings.
set-car! and set-cdr! are regular
procedures that change the parts of
pairs.
-----------------------------------------
Different kinds of mutation
The procedure sqr!-and-count-odd takes
a list of integers, mutates it by
squaring each element, and returns the
number of elements that were odd. For
instance:
(define lst (list 2 7 1 8 2 8))
(sqr!-and-count-odd lst)
-> 2
lst
-> (4 49 1 64 4 64)
Fill in the blanks in the
implementation:
(define (sqr!-and-count-odd lst)
(let ((counter _______))
(define (helper lst)
(if (________ (null? lst))
(______
(_______ lst (sqr (car lst)))
(if (odd? (car lst))
(______ _______ _______)
(helper _______))))
________
_______))
(define (sqr!-and-count-odd lst)
(let ((counter 0))
(define (helper lst)
(if (not (null? lst))
(begin
(set-car! lst (sqr (car lst)))
(if (odd? (car lst))
(set! counter (+ counter 1)))
(helper (cdr lst)))))
(helper lst)
counter))
-----------------------------------------
filter!
Let's write filter!, which is like
filter except it mutates its argument
list. Because the filtered list might
start from a different pair than the
original one, you need to use set! when
getting the results:
(define lst (list 3 1 4 1 5 9 2 6 5 3 5))
(set! lst (filter! even? lst))
lst
-> (4 2 6)
The easiest version of filter! to write
is a recursive one based on the
recursive non-mutation implementation
we've see before:
(define (filter f lst)
(cond ((null? lst) '())
((f (car lst))
(cons (car lst)
(filter f (cdr lst))))
(else (filter f (cdr lst)))))
What needs to be changed to make it
mutate?
;; Just change cons to set-cdr!:
(define (filter! f lst)
(cond ((null? lst) '())
((f (car lst))
(set-cdr! lst
(filter! f (cdr lst))))
(else (filter! f (cdr lst)))))
Writing an iterative version is
trickier, though. We'd like to use the
following pattern, but what do we put in
the blank?
(define (filter! f lst)
(define (helper l)
(cond ((null? l))
((f (car l))
(helper (cdr l)))
(else
_________________________
(helper (cdr l)))))
(helper lst)
lst)
There's really no way to get it to work just by filling in that blank,
which is why it's hard. There are two problems: first, to remove an
element, you need to change the cdr pointer of the previous element in
the list, but there's no easy way to get back to it. Second, you can't
just return "lst", since that always points at the first pair of the
original list, which you may not want to include in the result.
What should you do instead? I can think
of at least three approaches.
Approach 1 is the closest to the fill-in-the-blank version above, but
more extensive changes are needed. Solving each of the problems
mentioned above requires an additional variable, which you need to
use and update correctly.
(define (filter!-1 pred lst)
(let ((last '())
(head '()))
(define (helper lst)
(cond ((null? lst))
((pred (car lst))
(if (not (null? last))
(set-cdr! last lst))
(if (null? head)
(set! head lst))
(set! last lst)
(helper (cdr lst)))
(else
(helper (cdr lst)))))
(helper lst)
(if (not (null? last))
(set-cdr! last '()))
head))
Approach 2 takes advantage of the fact that the natural way of
iteratively going through a list reverses it. The iterative helper
"iter" is like reverse!, except that it removes pairs whose cars
don't satisfy the predicate. This gives a list with the right
elements, but backwards, so you need to call reverse! on it at the
end.
(define (filter!-2 f lst)
(define (iter from to)
(if (null? from)
to
(let ((next (cdr from)))
(cond ((f (car from))
(set-cdr! from to)
(iter next from))
(else
(iter next to))))))
(reverse! (iter lst '())))
Approach 3 is back to something more like approach 1, but more elegant
thanks to a clever trick. To avoid the special cases related to "last"
and "head" from approach 1, we can put a placeholder pair at the front
of the list. It provides an initial value for "last" it will always be
safe to modify, and its cdr plays the role of "head" remembering the
pointer to return.
(define (filter!-3 pred lst)
(let ((handle (cons '() lst)))
(define (helper last curr)
(cond ((null? curr))
((pred (car curr))
(helper curr (cdr curr)))
(else (set-cdr! last (cdr curr))
(helper last (cdr curr)))))
(helper handle lst)
(cdr handle)))
-----------------------------------------
Looking for loops
Using mutation, we can create data
structures that look like lists with
infinitely repeating sections:
(define four-thirds
(list 'one 'point 'three))
(set-cdr! (cddr four-thirds)
(cddr four-thirds))
(list-head four-thirds 5)
-> (one point three three three)
(list-head four-thirds 10)
-> (one point three three three three
three three three three)
Write a procedure has-loop? to check
whether its argument is a list with a
cdr-loop, like the above, or a regular
list.
Here's a brute-force but fairly simple approach: we'll know we have a
loop if the i-th and j-th pairs of the list counting from the front
are the same, but i < j. So we can just try all such pairs of
integers, being careful cover every pair and stop if we ever find an
end.
(define (has-loop-in-first-k? j lst)
(define (loop i)
(cond ((= i j) #f)
((eq? (list-tail lst i)
(list-tail lst j)) #t)
(else (loop (+ i 1)))))
(loop 0))
(define (has-loop? lst)
(define (iter k)
(cond ((null? (list-tail lst k)) #f)
((has-loop-in-first-k? k lst) #t)
(else (iter (+ k 1)))))
(iter 0))
There's a actually a cleverer way of doing this that uses just
pointers, and not counting, invented by Robert Floyd in 1967.