Homework 3 Solutions

Problem 1  TREE-MEMBER?
Obvious canditate for mutual-recursion:

(define (tree-member? elem tree)
  (or (equal? (datum tree) elem)
      (forest-member? elem (children tree))))

(define (forest-member? elem forest)
  (if (null? forest)
      #f
      (or (tree-member? elem (car forest))
          (forest-member? elem (cdr forest)))))

If you're more comfortable with HOFs, you can use MAP and ACCUMULATE

(define (tree-member? elem tree)
  (or (equal? (datum tree) elem)
      (ACCUMULATE (lambda (x y) (or x y))
                  #f
                  (MAP (lambda (T) (tree-member? elem T)) (children tree)))))


It might look uglier, but it's actually more beautiful, trust me.
**Note that we used a lambda instead of just using or because or is
a special form so we can't pass it as a procedure argument to a HOF.
Ask your TA or Min for more information.


Problem 2  ANCESTOR?
Whenever the datum is super we'll see if sub is a tree-member?; otherwise
we'll check for super in one of the sub-trees.

(define (ancestor? super sub tree)
  (if (equal? (datum tree) super)
      (tree-member? sub tree)
      (forest-ancestor? super sub (children tree))))

(define (forest-ancestor? super sub forest)
  (if (null? forest)
      #f
      (or (ancestor? super sub (car forest))
          (forest-ancestor? super sub (cdr forest)))))

This could also be done by absorbing the mutual recursion into a map and
accumulate

Problem 3  SHORTEST-LENGTH

(define (shortest-length tree)
  (+ 1 (forest-shortest-length (children tree))))

(define (forest-shortest-length forest)
  (cond ((null? forest) 0)  ; WARNING: NOT the base case of the recursion.
        ((null? (cdr forest)) (shortest-length (car forest)))
        (else (min (shortest-length (car forest))
                   (forest-shortest-length (cdr forest))))))

The shortest length of any tree is one plus the shorest length of a subtree
the procdure we wrote follows.

Second, note the 0 base case value in forest-shortest-length. We used 0
because (1) all tree-lengths are > 0 and (2) if we get to a leaf we want
to return zero so we don't add extra for non-existent children
We make sure to never get to that "base case" in a non-empty forest by adding
the base case that checks if the cdr of the forest is empty.

Problem 4  SHORTEST-PATH
When you first look at this problem it seems pretty hard. But you should 
notice that it is very similar to the previous problem. The difficult 
part is that in the forest-procedure for this problem, we would like to 
select the shorter list instead of the smaller number.

So let's define a helper procedure that compares two lists and return
the smaller one:

(define (pick-shorter ls1 ls2)
    (if (> (length ls1) (length ls2))
           ls1
           ls2)))

Now we are ready to define our tree and forest procedures:

(define (shortest-path tree)
   (if (null? (children tree))
          (list (datum tree))
       (cons (datum tree)
             (shortest-path-forest tree))))

(define (shortest-forest forest)
   (if (null? (cdr forest))
          (shortest-path (car forest))
       (pick-shorter
           (shortest-path (car forest))
           (shortest-forest (cdr forest)))))

NOTE:

WE CANNOT do something like this:

(define (shortest-path tree);; WRONG
       (cons (datum tree) ;; WRONG
             (shortest-path-forest tree))));; WRONG

(define (shortest-forest forest);; WRONG
   (if (null? forest) '();; WRONG
       (pick-shorter;; WRONG
           (shortest-path (car forest));; WRONG
           (shortest-forest (cdr forest)))));; WRONG

Because when the shortest-forest procedure goes to the base case
it will return the shortest list possible: '(), so then pick-shorter
will always pick '() over any other list.


; Problem 5  BST-INSERT

(define (bst-insert val bst)
  (cond ((null? bst) (make-bt val '() '()))
        ((< val (datum bst))
         (make-bt (datum bst)
                  (bst-insert val (left-child bst)) (right-child bst)))
        ((> val (datum bst))
         (make-bt (datum bst)
                  (left-child bst) (bst-insert val (right-child bst))))
        (else bst) )) ;; val equals datum so do nothing

; We always insert at the bottom of a BST. once we get to the bottom (a nil)
; we replace it with a leaf bst with val as the datum


; Problem 6  FIND

(define (find val btree)
  (cond ((null? btree) #f)
        ((< val (datum btree)) (find val (left-child btree)))
        ((> val (datum btree)) (find val (right-child btree)))
        (else #t))) ;; val equals datum so it is in the bst


; Problem 7  RANDOM-GENERATOR
; This is straightforward

(define-class (random-generator range)
  (instance-vars (count 0))
  (method (number)
    (set! count (+ count 1))
    (random range)))

; notice that we made count an instance var, since if we give ask an instance
; var as its argument, ask will return its value


; Problem 8  COKE-MACHINE

(define-class (coke-machine num-cokes price)
  (instance-vars (money 0))
  (method (deposit value)
    (set! money (+ money value))) 
  (method (coke)
    (cond ((< money price) "Not enough money")
          ((< num-cokes 1) "Machine empty")
          (else (let ((change (- money price)))
                  (set! money 0) ; since we're returning it as change
                  change))))
  (method (fill additional-cokes)
    (set! num-cokes (+ num-cokes additional-cokes))))

; Problem 9  MISS-MANNERS

(define-class (miss-manners core)
  (method (please message argument)
    (ask core message argument)))