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)) ------------------------------------------------------------