MIT 6.001                                       Fall, 1997
Instructor: A. Meyer

                 Recitation #7, Notes for Wed., 10/22/97

We spent half an hour reviewing the pattern matching Problem Set 5, in
particular explaining what a FINAL FORM was and approaches to finding
ALL-FINAL-FORMS of a datum (problem 8), which everyone found to be an
undoable problem on the problem set.

Then we explained the behavior of a LEARNER procedure which is a procedure
that is applicable to one number argument and returns #f if it has never
been applied to that number before, and returns #t otherwise.  In other
words, it "learns" the set of numbers to which it is ever applied.

For example, assuming LEARNER has never yet been applied to anything, we
would see behavior at the terminal like:
(learner 3)
;Value: #f

(learner 3)
;Value: #t

(learner 3)
;Value: #t

(learner 5)
;Value: #f

(learner 3)
;Value: #t

(learner 5)
;Value: #t

(learner 6)
;Value: #f

So at this point, the LEARNER procedure has learned the set {3, 5, 6}.

IN CLASS PROBLEM 1:  Complete the definition:

(define learner
  (let ((learned-set ...))
   (lambda (n)
      ....)))

Be sure to use the set abstraction for sets:

THE-EMPTY-SET
(ELEMENT-OF-SET? thing set)
(ADJOIN-SET thing set)
(EMPTY? set)



The procedure MAKE-LEARNER takes no arguments and returns a new learning
procedure.  For example, after
   (define learner1 (make-learner))
   (define learner2 (make-learner))
we would see the behavior:

(learner1 7)
;Value: #f

(learner1 7)
;Value: #t         ;LEARNER1 has learned 7 

(learner2 7)
;Value: #f         ;LEARNER2 has not learned 7 before

(learner2 7)
;Value: #t         ;NOW LEARNER2 has also learned 7

(learner2 9)
;Value: #f

(learner2 9)       ;LEARNER2 has learned 9
;Value: #t

(learner1 9)       ;LEARNER1 has not learned 9 before
;Value: #f

(learner1 6)       ;LEARNER1 has not learned 6 before
;Value: #f


IN CLASS PROBLEM 2: Complete the definition:

(define (make-learner) ...)


                               SOLUTION 1:
(define learner
  (let ((learned-set the-empty-set))
    (lambda (n)
      (or (element-of-set? learned-set)
          (begin
            (set! learned-set (adjoin-set n learned-set))
            #f)))))

;;SETS IMPLEMENTED AS UNORDERED LISTS WITH REPEATS
(define the-empty-set '())
(define (element-of-set? n set)
  (cond ((empty? set) #f)
        ((= n (car set) #t))
        (else (element-of-set? n (cdr set)))))
(define adjoin-set cons)
(define empty? null?)


                               SOLUTION 2:

(define (make-learner) <SAME AS THE DEF OF LEARNER>)

namely,

(define (make-learner)
  (let ((learned-set the-empty-set))
    (lambda (n)
      (or (element-of-set? n learned-set)
          (begin
            (set! learned-set (adjoin-set n learned-set))
            #f)))))