#lang scheme


;; Question 3 

;; We can make tree construction a little easier by defining two constructors:

(define (node t1 t2) (list 'node t1 t2))
(define (leaf x) (list 'leaf x))

; and we can manipulate them by defining some predicates:

(define (node? t) (and (eq? (car t) 'node) (= (length t) 3)))
(define (leaf? t) (and (eq? (car t) 'leaf) (= (length t) 2)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (a.1) 
;; Write a recursive function to compute the height of a tree.  Name this
;; function tree-height1.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; Write a recursive function to compute the yield of a tree (a list of
; the elements occurring at the leaves of the tree, from left to right).
; Name this function tree-yield1.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; (b.1)   Write a macro tree-case.  For example,
;;  (tree-case (node 3 4)
;;    ((node x y) (list x y))
;;    ((leaf x) (+ x 1))) => '(3 4)
;;  (tree-case (leaf 6)
;;    ((node x y) (list x y))
;;    ((leaf x) (+ x 1))) => 7
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (b.2) Write tree-yield and tree-height (recursively) using
;; tree-case.  Name these functions tree-yield2 and tree-height2.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (c.1) Write tree-fold (using recursion).
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (c.2) Write tree-yield and tree-height using tree-fold, 
;; name them tree-yield3 and tree-height3 respectively.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (d):
;; Once again, some helper functions are provided.
(define (add e1 e2) (list 'add e1 e2))
(define (sub e1 e2) (list 'sub e1 e2))
(define (mul e1 e2) (list 'mul e1 e2))
(define (div e1 e2) (list 'div e1 e2))
(define (num x) (list 'num x))
(define (add? t) (and (eq? (car t) 'add) (= (length t) 3)))
(define (sub? t) (and (eq? (car t) 'sub) (= (length t) 3)))
(define (mul? t) (and (eq? (car t) 'mul) (= (length t) 3)))
(define (div? t) (and (eq? (car t) 'div) (= (length t) 3)))
(define (num? t) (and (eq? (car t) 'num) (= (length t) 2)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (d.1) Write the evaluation function recursively, 
;; and name it eval1.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (d.2) Write match.  You may have to use a helper macro.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (d.3) Write eval recursively using match.  Name this function eval2.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;