Notes from Review

Here is the code that Felix drafted during today's lab.

(define-struct tree (lft rgt))
(define-struct leaf (arg))

;; A NumTree is one of:
;; - (make-leaf Number)
;; - (make-tree NumTree NumTree)

(define tree-123 (make-tree 
                  (make-tree (make-leaf 1) (make-leaf 2)) 
                  (make-leaf 3)))
(define tree-4567 (make-tree
                   (make-tree (make-leaf 4) (make-leaf 5))
                   (make-tree (make-leaf 6) (make-leaf 7))))

;; PROBLEM 
;; Design a function that finds the sum of all numbers in a NumTree

;; sum-tree : NumTree -> Number
(define (sum-tree t)
  (cond
    [(leaf? t) (leaf-arg t)]
    [(tree? t) (+ (sum-tree (tree-lft t))
                  (sum-tree (tree-rgt t)))]))

;; PROBLEM 
;; Design a function that finds the product of all numbers in a NumTree

;; prod-tree : NumTree -> Number
(define (prod-tree t)
  (cond
    [(leaf? t) (leaf-arg t)]
    [(tree? t) (* (prod-tree (tree-lft t))
                  (prod-tree (tree-rgt t)))]))
#|
;; PROBLEM
;; Abstract over the previous two functions to make writing such functions easier
;; operate-tree : (Number Number -> Number)  NumTree -> Number
(define (operate-tree operator t)
  (cond
    [(leaf? t) (leaf-arg t)]
    [(tree? t) (operator (operate-tree operator (tree-lft t))
                         (operate-tree operator (tree-rgt t)))]))

;; PROBLEM
;; Design a function that takes a NumTree t and a Number n and subtracts n from
;; every leaf of t

;; subn-tree : NumTree Number -> NumTree
(define (subn-tree t n)
  (cond
    [(leaf? t) (make-leaf (- (leaf-arg t) n))]
    [(tree? t) (make-tree (subn-tree (tree-lft t) n)
                          (subn-tree (tree-rgt t) n))]))
|#
;; PROBLEM
;; Abstract over the previous three (or four) functions to make a general
;; tree processing function.

;; fold-tree : (X X -> X) (Number -> X) NumTree -> X
(define (fold-tree tree-fcn leaf-fcn t)
  (cond 
    [(leaf? t) (leaf-fcn (leaf-arg t))]
    [(tree? t) (tree-fcn 
                (fold-tree tree-fcn leaf-fcn (tree-lft t))
                (fold-tree tree-fcn leaf-fcn (tree-rgt t)))]))

;; operate-tree : (Number Number -> Number)  NumTree -> Number
(define (operate-tree operator t)
  (fold-tree operator (lambda (x) x) t))

;; subn-tree : NumTree Number -> NumTree
(define (subn-tree t n)
  (fold-tree make-tree (lambda (x) (make-leaf (- x n))) t))


(equal? (operate-tree * tree-123)
        6)
(equal? (operate-tree + tree-4567)
        22)
(equal? (subn-tree tree-123 1)
        (make-tree (make-tree (make-leaf 0) (make-leaf 1))
                   (make-leaf 2)))

Lab 10: Review

The exam is this Thursday. So, today we review!

Sleeping Beauty

That's right, its lab time again!

Lab 8

You know the drill. Here are the notes.