recitation 8: more review & more tree problems

------------------------------------------------------------

quiz on tuesday,  makeup exam monday, email prof boning ASAP
covers lectures 1-7
(we'll talk about the picture language on Wednesday)

* 1 8.5x11 sheet of notes
* separate question & answer booklets
* pencil & eraser recommended
* don't spend too long on any one problem
* don't leave anything blank, we will give partial credit
* be concise & choose good variable names
  - you have to fit your answer in the box provided

------------------------------------------------------------

* what does it mean when we say that a procedure has "inherent data"?

(define (cons a b) (lambda (x) (if x a b)))
(define (car c) (c #t))
(define (cdr c) (c #f))

* what's a higher order procedure?

* what's a "side effect"?
  - "state" change
  - expressions that have side effects often do not 
    return a value (the value of the expression is undefined)

* what side effects have we seen so far?
  - define, errors, display, draw-line

------------------------------------------------------------

* what's a tree?
  - a list of lists

* stylized tree diagrams

* (problems from recitation 7 handout)

* write a procedure (make-power-tree n) that returns a binary tree
  (i.e. a tree with two branches at each node) that is n levels deep.
  the leaf values at the bottom of the tree should be the total number
  of leaves.

  (make-power-tree 0) -> 1
  (make-power-tree 1) -> (2 2)
  (make-power-tree 2) -> ((4 4) (4 4))

* write a procedure (map-tree op tree) that returns a new tree, with
  each leaf replaced by (op leaf) analogous to map on lists.  An elegant
  solution uses map.

* write a procedure (fold-right-tree op init tree) that gathers the
  leaves of the trees using op, analogous to fold-right on lists.  An
  elegant solution uses map & fold-right

* write (count-leaves tree) that counts the leaves in a tree.  It
  should use map-tree & fold-right-tree and should not call itself.

------------------------------------------------------------

* when should we use define?
  - top level definitions of global variables
  - nested procedures

* when should we use let?
  - to define local variables 
  - to avoid repeated calculations
  - to make code easier to read by naming complex things

* when should we use lambda?
  - to create a procedure

* when should we use "nested lambdas"?
  - to define a procedure whose return type is a procedure!

* when should we use begin?
  - to execute multiple statements in a particular order
  - since the values of all but the last statement are thrown 
    away, they are only executed for their side effects

* when should we use if/cond?
  - to branch during execution
  - use cond if you have alot of cases

* when should we use and/or?
  - when you have multiple conditions/predicates to check for if/cond
  - sometimes used in "weird" ways...  just follow the rules for 
    evaluating these special forms

* when should we write helper functions?
  - to avoid repeated code
  - often necessary to write iterative version of procedure

------------------------------------------------------------

We haven't learned mutation yet.  You don't need it for any of the
problems we've given you so far.  But some of you are still trying to
think like java/C/C++/pascal/basic programmers.  For example:

  BAD:  doesn't even execute!      
      (define tmp 1)
      (define count-up-to 
         (lambda (x)
            (if (> tmp x)
                "done"
                (begin (display tmp)
                       (define tmp (+ 1 tmp))
                       (count-up-to x)))))
      
  GOOD:  make a helper function to keep track of extra variable      
      (define count-up-to 
        (lambda (x)
          (helper x 1)))
      
      (define helper
         (lambda (x tmp)
            (if (> tmp x)
                "done"
                (begin (display tmp)
      		 (helper x (+ 1 tmp))))))
      
    nested scope:
      (define (count-up-to x)
        (define (helper x tmp)
          (if (> tmp x)
      	"done"
      	(begin (display tmp)
      	       (helper x (+ 1 tmp)))))
        (helper x 1))

    note: Since it's nested and x is constant throughout 
          execution, helper doesn't need the x!
      (define (count-up-to x)
        (define (helper tmp)
          (if (> tmp x)
	      "done"
	      (begin (display tmp)
		     (helper (+ 1 tmp)))))
        (helper 1))

------------------------------------------------------------