Tutorial notes #7 for 4/2 or 4/3/2007

TA:       Stephen McCamant
Email:    smcc@mit.edu
Location: 36-113A or 36-115
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,

- 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

- Question 18 was open-ended, so to get
  maximum credit, we were looking for an
  answer that was both original and

  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

  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

- Useful procedure: for-each is like
  map, but doesn't make a list of the

- 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

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

(define lst (list 2 7 1 8 2 8))
(sqr!-and-count-odd lst)
-> 2
-> (4 49 1 64 4 64)

Fill in the blanks in the

(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))
            (set-car! lst (sqr (car lst)))
            (if (odd? (car lst))
                (set! counter (+ counter 1)))
            (helper (cdr lst)))))
    (helper lst)


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))
-> (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

;; 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)))
           (helper (cdr l)))))
  (helper 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)))
             (helper (cdr lst)))))
    (helper lst)
    (if (not (null? last))
        (set-cdr! last '()))

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

(define (filter!-2 f lst)
  (define (iter from to)
    (if (null? from)
        (let ((next (cdr from)))
          (cond ((f (car from))
                 (set-cdr! from to)
                 (iter next from))
                 (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

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

(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.