6.001, Spring 2005—Recitation 8 16.001—Structure and Interpretation of Computer ProgramsSpring 2005Recitation 8Quiz 1 ReviewPossible review topicsWe’re not just going to work straight through the problems on this recitation sheet, because I wantto know what you want to review. Here are some possible topics:• Stupid evaluator tricks• Recursion• Abstraction• Lexical scoping• Box-and-pointer diagrams• Desugaring• map, filter, and fold-right• TypesEvaluationEvaluate the following expressions. If they generate an error, give a general description of the error.If they result in a procedure, give the type of the procedure. If they result in a list/pair structure,draw the box-and-pointer for the structure.(+ 3 4)(7)(if (+ 3 4) 8 9)(define x 17)(lambda (y) x)((lambda (x y) (x y)) (lambda (z) (lambda (a) (+ a z))) 8)(cons 1 (list 3 4 (cons 5 6)))(let ((a (list 4 5)))6.001, Spring 2005—Recitation 8 2(cons a (list 3 a)))(list (list list) nil)Some rather ridiculous problems(lambda (f g x) ((f g) x))(lambda (a b c d)(if (a b) (b c) (d c)))(fold-right map (list twice thrice) (list twice thrice))map, filter, and fold-rightSuppose x is bound to the list (1 2 3 4 5 6 7). Using map, filter, and/or fold-right, write anexpression involving x that returns:1. (1 4 9 16 25 36 49)2. (1 3 5 7)3. ((1 1) (2 2) (3 3) (4 4) (5 5) (6 6) (7 7))4. (1 (2 (3 (4 (5 (6 (7 ())))))))5. ((2) ((4) ((6) ())))6. (7 6 5 4 3 2 1)7. The maximum element of x: 76.001, Spring 2005—Recitation 8 3tree-manip: fold-right on crackWe want to generalize fold-right to do stuff over trees. The procedure looks like this:(define (tree-manip tree init leaf accum)(cond ((null? tree) init)((not (pair? tree)) (leaf tree))(else (accum(tree-manip (car tree) init leaf accum)(tree-manip (cdr tree) init leaf accum)))))Here’s a tree to use this on: (define test-tree (list 1 (list 2 (list 3 (list 4) 5) 6)7)).Now, using appropriate arguments to tree-manip:1. Count the number of leaves on the tree.2. Apply a certain procedure, proc, to each leaf of the tree. (Think of this as tree-map.)3. Flatten the tree, so that test-tree becomes (1 2 3 4 5 6 7).4. Deep-reverse the tree, so that test-tree be com es (7 (6 (5 (4) 3) 2) 1).5. Take the product of all the leaves of the tree .6. Remove the even-valued leaves of the tree, so for exam ple, test-tree becomes (1 ((3 ()5)) 7).7. If there is a subtree of the tree whose leaves add up to less than 10, replace it by its to-tal. Example: (((1 2) (2 3)) 8 (5 (3 4))) becomes (8 8 (5 7)). Don’t worry
View Full Document
Unlocking...