SAMPLE SOLUTIONS to recitation 7: some practice problems -------------------------------------------- * write down the rules for evaluating expressions in scheme 1. If self-evaluating, return value. 2. If a name, return value associated with name in environment. 3. If a special form, do something special. 4. If a combination, then a. Evaluate all of the subexpressions of combination (in any order) b. Apply the operator to the values of the operands (arguments) and return result -------------------------------------------- * write down the rules for application of a procedure 1. if primitive procedure, just do it 2. if compound procedure - evaluate the body of the procedure with each formal parameter replaced by the corresponding argument value. - 1 or more expressions in the body are evaluated in order return the value of the last expression * what's the difference between a primitive procedure & a compound procedure? primitive procedures are built-in. compound procedures are created with a lambda. -------------------------------------------- * fill in the blanks: To find the value of a COMBINATION: a. first, find the value of subexpressions b. then, APPLY the value of the value of the first subexpression (the operator) to the the value of the remaining subexpressions (the arguments). -------------------------------------------- * list the special forms we've learned so far. For each special form, write down the syntax (and/or an example of its use), the special rules for evaluation, and describe why it must be special form (why can't we use the regular rules for application?) define, lambda, if, cond, and, or, begin, let -------------------------------------------- (intersection (list 1 2 3 4) (list 3 5 1 6)) -> (1 3) * type: list,list -> list * implement intersection using map, filter, and/or fold-right (define (intersection a b) (filter (lambda (x) (member x b)) a)) -------------------------------------------- (apply-all (list abs square cube inc) -4) -> (4 16 -64 -3) * type: list(A->A),A -> list(A) * implement apply-all recursively (define (apply-all ops arg) (if (null? ops) nil (cons ((car ops) arg) (apply-all (cdr ops) arg)))) * implement apply-all using map, filter and/or fold-right (define (apply-all ops x) (map (lambda (op) (op x)) ops)) -------------------------------------------- (append (list 1 2 3) (list 4 5 6)) -> (1 2 3 4 5 6) * type: list,list -> list * implement append recursively (define (append a b) (if (null? a) b (cons (car a) (append (cdr a) b)))) * implement append using map, filter and/or fold-right (define (append a b) (fold-right cons b a)) -------------------------------------------- (reverse (list 1 2 3 4)) -> (4 3 2 1) * type: list -> list * implement reverse recursively using append (define (reverse lst) (if (null? lst) nil (append (reverse (cdr lst)) (list (car lst))))) * implement reverse iteratively (define (reverse lst) (define (reverse-helper lst answer) (if (null? lst) answer (reverse-helper (cdr lst) (cons (car lst) answer)))) (reverse-helper lst nil)) -------------------------------------------- (define my-tree (list 1 (list 2 3 (list 4 5)) (list (list 6)))) my-tree -> (1 (2 3 (4 5)) ((6))) * draw the box & pointer diagram for my-tree * draw a "stylized tree diagram" for my-tree * how are they related? -------------------------------------------- (define (leaf? tree) (not (pair? tree))) (define (tree-manip leaf-op init merge tree) (if (null? tree) init (if (leaf? tree) (leaf-op tree) (merge (tree-manip leaf-op init merge (car tree)) (tree-manip leaf-op init merge (cdr tree)))))) * what's the type of tree-manip? tree-manip: A->B, B, (B,B->B), tree -> B -------------------------------------------- * use tree manip to square every element of a tree (define (square-tree tree) (tree-manip square nil cons tree)) (square-tree my-tree) -> (1 (4 9 (16 25)) ((36))) * use tree-manip to compute the product of all the even-valued leaves of the tree (assume a tree of integers) (define (product-even tree) (tree-manip (lambda (x) (if (odd? x) 1 x)) 1 * tree)) (product-even my-tree) -> 48 * use tree-manip flatten a tree (define (flatten tree) (tree-manip (lambda (x) (list x)) nil append tree)) (flatten my-tree) -> (1 2 3 4 5 6) * use tree-manip to "deep-reverse" a tree (reverse the order of children at each node) (define (deep-reverse tree) (tree-manip (lambda (x) x) nil (lambda (x y) (append y (list x))) tree)) (deep-reverse my-tree) -> (((6)) ((5 4) 3 2) 1) * use tree-manip to sum up the values of the leaves of the tree (assume a tree of numbers) (define (sum-leaves tree) (tree-manip (lambda (x) x) 0 + tree)) (sum-leaves my-tree) -> 21 * use tree-manip to create a new tree, which keeps the odd-valued leaves of the original tree within the same tree structure, but removes even valued leaves. (assume a tree of integers) (define (keep-odd-leaves tree) (tree-manip (lambda (x) (if (even? x) nil x)) nil (lambda (x y) (if (null? x) y (cons x y))) tree)) (keep-odd-leaves my-tree) -> (1 (3 (5))) (keep-odd-leaves (list 1 2 3 4 5 6)) -> (1 3 5) (keep-odd-leaves (list 2 4 6)) -> nil (keep-odd-leaves (list (list 1) (list 4) (list 6))) -> ((1)) * for each of the above exercises, write down the types of arguments & return value for the calls to tree-manip. Make sure it "type checks". -------------------------------------------- For each expression below, indicate the value & type. If it's value is undefined, or it produces an error or infinite loop, indicate so. (let ((* /) (/ *)) (/ 12 (* 6 3))) * value: 24 * type: number ((lambda (x + y) (+ x y)) 3 * 4) * value: 12 * type: number (define (inc x) (+ 1 x)) * value: undefined * type: undefined inc * value: procedure * type: number -> number (define (foo f) (lambda (x) (f (f (f x))))) * value: undefined * type: undefined foo * value: undefined * type: (A -> A) -> (A -> A) ((foo inc) 0) * value: 3 * type: number ((foo (foo inc)) 0) * value: 9 * type: number (((foo foo) inc) 0) * value: 27 * type: number -------------------------------------------- fibonacci: f(0) = 1 f(1) = 1 f(n) = f(n-1) + f(n-2), for n >= 2 * write a recursive procedure to implement fibonacci (define (fibonacci x) (cond ((= x 0) 1) ((= x 1) 1) (else (+ (fibonacci (- x 1)) (fibonacci (- x 2)))))) * write an iterative procedure to implement fibonacci Note: this version should do something smarter... and not duplicate work (define (fibonacci-iterative x) (define (helper n fn fn-1) (if (= n x) fn (helper (+ n 1) (+ fn fn-1) fn))) (helper 0 1 0)) * use the substitution model (in gory detail, take small steps) to evaluate a small example of each of your procedures. Come up with the formula for the number of steps ("height") and memory requirements ("width") as a function of the input. Generalize this to an order of growth for each. Note: the math here is actually a topic for 6.042, but we just want you to get a flavor for it... -------------------------------------------- * what's the difference between applicative order & normal order evaluation? applicative order evaluates all the subexpressions first and then applies the operator to the arguments. normal order is lazy. normal order substitutes the unevaluated expressions into the body of the procedure and evaluates them only as needed. * which does scheme use? scheme is applicative order. -------------------------------------------- write an expression for ?, so that the expressions below evaluate as indicated. (define foo (lambda (x y) (if (< x y) (abs x) (- y)))) (foo -5 3) => 5 (foo 2 7) => 2 (foo 7 4) => -4 (foo 10 -4) => 4 (define bar (lambda (x) (cond ((= x 4) 6) ((= x 5) 7) ((= x 6) (/ x 0)) ((= x 7) (lambda () 1))))) (bar 4) => 6 (bar 5) => 7 (bar 6) => error, divide by zero (bar 7) => procedure -------------------------------------------- (define mystery (lambda (a b) (mystery-meat 0 a b))) (define mystery-meat (lambda (c a b) (if (> a b) c (mystery-meat (+ c a) (+ a 1) b)))) * write an equivalent procedure that generates a recursive process: (define clarity (lambda (a b) (if (> a b) 0 (+ a (clarity (+ a 1) b))))) -------------------------------------------- * Design a data structure to store information about students in 6.001. For each student, we want to store: their first name (string), intended major (number), and their height (number). Explain in words the contract between your constructor & accessor functions. Sketch out the box & pointer diagram for a simple example. (define (make-student name major height) (list name major height)) (define (get-student-name student) (car student)) (define (get-student-major student) (cadr student)) (define (get-student-height student) (caddr student)) (define (make-empty-student-list) nil) (define (add-student student student-list) (cons student student-list)) * Design an alternate data structure to store the same information. Try to come up with something really different, and explain in what cases your first design might be more useful, and in what cases your second design might be more useful. Write the following functions. Use your accessors & constructors. Don't violate the abstraction barrier. (What's an abstraction barrier?) Use map, filter & fold-right, when appropriate. Also, write helper functions to make your code concise and easy to read. * Write a function that takes in a list of student names, and a list of their corresponding heights and returns a student list, with everyone's major set as undeclared. Modify your data structure design as necessary so that you can store and detect undeclared majors. In your documentation spell out any assumptions you have made about the input. (define (initialize-student-list names heights) (if (null? names) (make-empty-student-list) (add-student (make-student (car names) (car heights) "undeclared") (initialize-student-list (cdr names) (cdr heights))))) (initialize-student-list (list "Ben" "Alyssa" "Louis") (list 70 67 72)) * Write a function that takes in a student-list, a student's first name, and a new major, and returns a new student list with the major declared appropriately. * Write a function that takes in a student-list and returns a student list where the undeclared majors have been set by the length of each students first name. ("Ben" will be course 3, and "Alyssa" will be course 6). * Write a function that takes in a student-list and returns the average height of students in the class with a particular major. Make sure you handle undeclared majors and majors with no students. * Write a function that takes in a student-list and returns a list of the student names sorted by student height. --------------------------------------------