Quiz #1

Problem 1
a) This is a message passing data abstraction.

b) A pair shares similar storage characteristics because it stores two elements and we can retrieve those two elements from it.

c) The selectors would be:

(define (mp-car pair) (pair 'first))
(define (mp-cdr pair) (pair 'second))

Problem 2

Constructors:

(make-btree datum left right) returns a btree

Selectors:

(get-datum btree) returns a datum

(get-left btree) returns a btree

(get-right btree) returns a btree

(get-children btree) returns a list of non-empty btrees

Predicates:

(empty-btree? btree) retunrs a boolean

Constants:

empty-btree is a btree

(define (reorder btree)
  (if (empty-btree? btree) btree
      (let ((left (get-left btree))
            (right (get-right btree)))
        (let ((left? (not (empty-btree? left)))
              (right? (not (empty-btree? right))))
          (let ((datum (get-datum btree))
                (left-datum (if left? (get-datum left)
                                      #f))
                (right-datum (if right? (get-datum right)
                                        #f)))
            (cond ((and (not left?) (not right?)) btree)
                  ((or (not left?) (> right-datum left-datum))
                   (if (> right-datum datum)
                       (make-btree right-datum
                                   left
                                   (make-btree datum
                                               (get-left right)
                                               (get-right right)))
                       btree))
                  (else (if (> left-datum datum)
                            (make-btree left-datum
                                        (make-btree datum
                                                    (get-left left)
                                                    (get-right left))
                                        right)
                            btree)) ))))))

b) There are two ways of approaching this problem reasonably. One uses get-left and get-right. The other uses get-children. If seen on an exam, you might have something that gets a list of children, so I'm going to show both ways of writing this.

(define (tree-height btree)
  (if (empty-tree? btree) 0
      (+ 1 (max (tree-height (get-left btree))
                (tree-height (get-right btree)) ))))

Or a possibility is:

(define (tree-height btree)
  (define (max-height btreelist)
    (if (empty? btreelist) 0
        (max (tree-height (car btreelist))
             (max-height (cdr btreelist))) ))
  (if (empty-tree? btree) 0
      (+ 1 (max-height (get-children btree))) ))

c) I continued to think about this problem and determined that it doesn't have to be done in any given order. Preorder, postorder, or inorder all work. Below is postorder, but I'll include a clearer version of all three.

(define (reorder-pass btree)
  (if (empty-tree? btree) btree
      (reorder (make-btree (get-datum btree)
                           (reorder-pass (get-left btree))
                           (reorder-pass (get-right btree)) )) ))

PostOrder

(define (reorder-pass btree)
  (if (empty-btree? btree) btree
      (let ((left (reorder-pass (get-left btree)))
            (right (reorder-pass (get-right btree))))
        (reorder (make-btree (get-datum)
                             left
                             right)) ) ) )

PreOrder

(define (reorder-pass btree)
  (if (empty-btree? btree) btree
      (let ((left (reorder-pass (get-left btree)))
            (right (reorder-pass (get-right btree))))
        (reorder (make-btree (get-datum)
                             left
                             right)) ) ) )

InOrder

(define (reorder-pass btree)
  (if (empty-tree? btree) btree
      (let ((left (reorder-pass (get-left btree))))
        (let ((root (reorder (make-btree (get-datum btree)
                             left
                             (get-right btree) ))))
          (let ((right (reorder-pass (get-right root))))
            (make-btree (get-datum root)
                        (get-left root)
                        right) ) ) ) ) )

(define (full-reorder btree)
  (define (full-reorder-iter btree n)
    (if (= n 0) btree
        (full-reorder-iter (reorder-pass btree) (- n 1)) ))
  (full-reorder-iter btree (tree-height btree)))

Problem 3

a) (cons 'a (cdr (car (list '(1 2) 3 4))))

.---.---.  .---.---.
| * | *-+->| * | / |
`-|-'---'  `-|-'---'
  V          V
  a          2

prints as:  (a 2)

b) (cons '(cons 4 5) (list 7 8))

.---.---.  .---.---.  .---.---.
| * | *-+->| * | *-+->| * | / |
`-|-'---'  `-|-'---'  `-|-'---'
  |          V          V
  |          7          8
  V
.---.---.  .---.---.  .---.---.
| * | *-+->| * | *-|->| * | / |
`-|-'---'  `-|-'---'  `-|-'---'
  V          V          V
 cons        4          5

prints as:  ((cons 4 5) 7 8)