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.

Lab 7

1. The submission server.
   • Check your exam grade!
2. From cons to list: some brain teasers.

   Note: these exercises are not fundamental to computer science. However, doing them may help you better understand some output you see later on.

   Look at the expressions below. Which ones represent the same list? How long is each list?

   Hint: there are really only six distinct values described below. Go ahead and divide a piece of paper up into six boxes, and then put each expression where it belongs.

   (you can test your answers by cut-and-pasting expressions into the Interactions Window and seeing if they come out the same. Or use equal? to be sure. Use length in the Interactions Window to verify how long each list is)
   • empty
   • (cons 1 empty)
   • (list 1)
   • (list)
   • (cons 1 (cons 2 empty))
   • (cons 1 (cons 2 (cons 3 empty)))
   • (cons (cons 1 (cons 2 empty)) (cons 3 empty))
   • (cons (cons 1 (cons 2 empty)) (cons (cons 3 (cons 4 empty)) empty))
   • (list 1 2)
   • (list 1 2 3)
   • (list (cons 1 (cons 2 empty)) 3)
   • (cons (list 1 2) (cons (list 3 4) empty))
   • (list (list 1 2) 3)

   In general, we urge you to use cons rather than list within the code for your functions. The list function is most appropriate for writing test data in your examples, because it is succinct and the reader can easily see, when looking at a list expression, how many elements make up the list and what the elements themselves are (e.g., nested lists).

3. XML, HTML, Music, and more:

   Now the "real" notes

   Oh, and just because I'm pedantic:

   ;; An XHTML is a (cons Symbol (cons empty List-of-XHTML empty))
   
   ;; A List-of-XHTML is one of:
   ;; - empty
   ;; - (cons String List-of-XHTML)
   ;; - (cons XHTML List-of-XHTML)
   
   ;; A List-of-string is one of:
   ;; - empty
   ;; - (cons String List-of-string)
   

Exercises for today's lab.

NOTE: the teachpack at the link below is semi-broken. Please use the html.ss in this zip file instead. Exercises for today's lab. Make sure that you understand the problems before you start them. Play with example instances of the data! Also make sure that you work out your examples before you start coding.

Lab 5 notes

The notes for today's lab. If you finish early (as if that ever happens), feel free to try the extra problems from last week's lab.

Lab 4 notes

Lab 4 notes are here. [EDIT] For the punchline for the last section (and a whole new set of problems), go here.