Here are the solutions to the review questions. Although I made a point of ignoring the representation of trees when working the problems, we do need to come up with a concrete Scheme representation to check them on the computer. We'll use the standard definitions of MAKE-TREE, CHILDREN and DATUM from lecture: (define make-tree cons) (define datum car) (define children cdr) (define (leaf? t) (null? (children t))) Let's also build up this tree: (6) / | \ / | \ (5) (3) (4) / \ (1) (2) (define leaf1 (make-tree 1 '())) (define leaf2 (make-tree 2 '())) (define leaf3 (make-tree 3 '())) (define leaf4 (make-tree 4 '())) (define node1 (make-tree 5 (list leaf1 leaf2))) (define node2 (make-tree 6 (list node1 leaf3 leaf4))) Problem 1 (define (tree-sum tree) (if (leaf? tree) (datum tree) ;; note: return datum of leaf, not zero (accumulate + (datum tree) (map tree-sum (children tree))))) The LEAF? base case is not really needed, so this works too: (define (tree-sum tree) (accumulate + (datum tree) (map tree-sum (children tree)))) ... but it's harder to read. Here is a version without MAP and ACCUMULATE. Instead, we'll use a helper to act on a forest, a list of trees: (define (tree-sum tree) (if (leaf? tree) (datum tree) (+ (datum tree) (sum-forest (children tree))))) (define (sum-forest forest) (if (null? forest) 0 (+ (tree-sum (car forest)) (sum-forest (cdr forest))))) Importantly, you *can* call CAR and CDR on a forest since a forest is a list of trees. You cannot however call CAR on a tree, since the only selectors defined for trees are CHILDREN and DATUM. Problem 2 A lot of people miss the fact that the range of COUNT-NODES is not a number, list or boolean. It's a tree! How do you make a tree? Use MAKE-TREE. (define (count-nodes tree) (if (leaf? tree) (make-tree 1 '()) ;; even in the base case return a tree, not 1 (let ((kids (map count-nodes (children tree)))) ;; KIDS is a *list of trees* because COUNT-NODES both takes and returns a tree ;; we want KIDS to ultimately become the children of our new tree, but before that ;; can happen, we need to add up the data in their root nodes (and add one to it) ;; to form the datum of the new tree (let ((new-datum (accumulate + 1 (map datum kids)))) (make-tree new-datum kids))))) Let's try this out on the simple tree: (a) / | \ / | \ (c) (b) (g) / \ (d) (e) It is not a leaf, so go into recursive case: Assuming that COUNT-NODES works as advertised, (3) KIDS = ( / \ (1) (1) ) (1) (1) KIDS is a list of three trees! Let's call DATUM on each one, yielding the list (3 1 1). NEW-DATUM is (accumulate + 1 (3 1 1)) ==> 6 Putting KIDS together with NEW-DATUM gives: (6) / | \ / | \ (3) (1) (1) / \ (1) (1) Problem 3 With MAP/ACCUMULATE: (define (fringe tree) (if (leaf? tree) (list (datum tree)) ;; must return a *list* in all cases (accumulate append () (map fringe (children tree))))) Can also do it with APPLY: (define (fringe tree) (if (leaf? tree) (list (datum tree)) (apply append (map fringe (children tree))))) Problem 4 The depth of a tree is one more than the depth of its deepest child. That is, given the tree (6) / | \ / | \ (5) (3) (4) / \ (1) (2) (5) ... it's deepest child is / \ (1) (2) ... the depth of which is 2. The depth of the whole tree then, is one more than that: 2+1=3. (define (depth tree) (if (leaf? tree) 1 (+ 1 (accumulate max 0 (map depth (children tree)))))) I can give ACCUMULATE MAX a null value of zero here since the depth of a tree cannot be negative. As before, you do not even need the explicit base case: (define (depth tree) (+ 1 (accumulate max 0 (map depth (children tree))))) Problem 5 How do you find out how many children a tree has? Take the LENGTH of it's CHILDREN. Remember, CHILDREN returns a list of trees. (define (num-kids tree) (length (children tree))) (define (max-children tree) (accumulate max (num-kids tree) (map max-children (children tree)))) Here is a recursive version: (define (max-children tree) (if (leaf? tree) 0 (max (num-kids tree) ;; compare number of children of this tree (max-kids-in-forest (children tree))))) (define (max-kids-in-forest forest) (if (null? forest) 0 (max (max-children (car forest)) (max-kids-in-forest (cdr forest))))) Problem 6 (define (equal-tree? t1 t2) (and (equal? (datum t1) (datum t2)) (= (length (children t1)) (length (children t2))) (not (member #f (map equal-tree? (children t1) (children t2)))))) This version uses the expanded version of MAP which we did not cover this summer. MAP actually takes N lists and a function that can take N arguments; it applies the function to the first elements of each of the N lists, then to the second elements, etc. For example: STk> (map list '(1 2 3 4) '(a b c d) '(10 10 10 10)) ((1 a 10) (2 b 10) (3 c 10) (4 d 10)) STk> (map list-ref '((a b c d) (e f g) (h i) (j k l m)) '(0 1 0 3)) (a f h m) All N lists given to MAP must have the same length! But here is a version that uses mutual recursion: (define (equal-tree? t1 t2) (and (equal? (datum t1) (datum t2)) (= (length (children t1)) (length (children t2))) (equal-forest? (children t1) (children t2)))) (define (equal-forest? f1 f2) (or (null? f1) ;; need only check one since they're the same length (and (equal-tree? (car f1) (car f2)) (equal-forest? (cdr f2) (cdr f2))))) Problem 7 (define (nodes-at-depth tree n) (if (= n 1) (list (datum tree)) (accumulate append '() (map (lambda (subtree) (nodes-at-depth subtree (- n 1))) (children tree))))) Problem 8 (define (tree-member tree x) (or (equal? x (datum tree)) (accumulate (lambda (a b) (or a b)) ;; cannot accumulate OR #f (map (lambda (subtree) (tree-member subtree x)) (children tree))))) Problem 9 I don't see a way to solve this problem as cleanly as the others, so I'll use TREE-MEMBER as a helper. (define (ancestor tree w1 w2) ;; need extra variable to hold the closest ancestor found ;; so far -- so define helper (define (ancestor-help tree closest) (let ((child-with-both (contains-forest? w1 w2 (children tree)))) ;; is there a child of tree that contains both w1 and w2 (if child-with-both ;; if yes, then make its datum the new closest ancestor (ancestor-help child-with-both (datum child-with-both)) ;; otherwise we're done closest))) ;; returns the tree in the forest that contains both w1 and w2 ;; returns #f if no such child exists (define (contains-forest? w1 w2 forest) (cond ((null? forest) #f) ((and (tree-member (car forest) w1) (tree-member (car forest) w2)) (car forest)) (else (contains-forest? w1 w2 (cdr forest))))) ;; originally, the closest ancestor node will be the root of the tree (ancestor-help tree (datum tree))) Problem 10 (define (siblings? tree x1 x2) (let ((my-kids (map datum (children tree)))) (or (and (member x1 my-kids) (member x2 my-kids)) (siblings-in-forest? x1 x2 (children tree))))) (define (siblings-in-forest? x1 x2 forest) (if (null? forest) #f (or (siblings? (car forest) x1 x2) (siblings-in-forest? x1 x2 (cdr forest))))) Problem 11 (define (path-to tree x) (cond ((equal? (datum tree) x) (list (datum tree))) ((leaf? tree) #f) (else (let ((subpath (accumulate (lambda (a b) (or a b)) (map (lambda (child) (path-to child x)) (children tree))))) (and subpath (cons (datum tree) subpath)))))) Problem 12 ;; this handles the top-level list (define (deep-member x lst) (cond ((equal? x lst) #t) ((not (pair? lst)) #f) (else (member-helper x lst)))) ;; this goes deeply into the list elements (define (member-helper x lst) (cond ((null? lst) #f) ((deep-member x (car lst)) #t) (else (member-helper x (cdr lst))))) Problem 13 (define (deep-member x lst) (accumulate (lambda (sublist result) (or (equal? x sublist) (and (pair? sublist) (deep-member x sublist)) result)) #f lst)) Problem 14 The idea here is that the depth of a list is one more than the depth of its deepest sublist. That is, given the list '((1 (2)) (3)), which can be represented as a box and pointer diagram: DEPTH +---+---+ +---+---+ --->| o | o-|-------------->| o | / | 1 +-|-+---+ +-|-+---+ | | | V +---+---+ +---+---+ +---+---+ | o | o-|--->| o | / | | o | / | 2 +-|-+---+ +-|-+---+ +-|-+---+ | | | V V V 1 +---+---+ 3 | o | / | 3 +-|-+---+ | V 2 The depth of the list is 3. The depth of the deepest sublist (1 (2)) is 2, which is one less than the depth of the whole thing. (define (depth lst) (if (not (pair? lst)) 0 (max (+ (depth (car lst)) 1) (depth (cdr lst))))) Let's trace through (depth '((1 (2)) (3))). But we will only go up to the first recursive call -- at which point we'll assume that DEPTH works as it is supposed to. You can always make this assumption! Trust the recursion. 1. (depth '((1 (2)) 3)) 2. (max (+ 1 (depth '(1 (2)))) ;; trust the recursion here! (depth '((3)))) ;; assume DEPTH works! 3. (max (+ 1 2) 2) 4. 3 Here is a way to write DEPTH with MAP and ACCUMULATE. (define (depth lst) (if (not (pair? lst)) 0 (+ 1 (accumulate max 0 (map depth lst))))) And now just ACCUMULATE: (define (depth lst) (accumulate (lambda (x depth-so-far) (if (pair? x) (max (+ (depth x) 1) depth-so-far) depth-so-far)) 1 lst)) Problem 15 An important part of doing this problem is to realize that LONGEST-SUBLIST must only be called on lists. Calling it on, say, 24 does not make sense since 24 is not a list -- hence it does not have a longest sublist. The empty list, however, is a perfectly good base case since the longest sublist of the empty list is itself. (define (longest-sublist lst) (cond ((null? lst) '()) ((not (pair? (car lst))) (longest lst (longest-sublist (cdr lst)))) (else (longest lst (longest (longest-sublist (car lst)) (longest-sublist (cdr lst))))))) The second clause keeps us from calling LONGEST-SUBLIST on something that is not a pair. In this clause, we need only compare LST to the longest sublist found in the cdr of LST. In the else clause, three lists must be compared: 1. The original list, LST 2. The longest sublist found in the car of LST, and 3. The longest sublist found in the cdr of LST. The LONGEST helper serves as the recursive combiner. Below is another solution. Again, notice that it too checks that SUB is a list before calling LONGEST-SUBLIST on it. The great thing about this solution is that comparing the toplevel list LST to the longest sublist found in its car or cdr is handled in the accumulation, because LST serves as the null value. Hence, we start the accumulation with LST as the longest list found so far. If there is a longer list in deeper inside LST, LONGEST and the recursive call to LONGEST-SUBLIST find it. (define (longest-sublist lst) (accumulate (lambda (sub long) (if (list? sub) (longest (longest-sublist sub) long) long)) lst lst)) There is one case where the two versions of LONGEST-SUBLIST do not return the same list, although neither is strictly wrong. What is that case? (Hint: Look at the assumption we made about the argument to LONGEST-SUBLIST.) Then there is this beauty: (define (longest-sublist lst) (accumulate longest lst (map longest-sublist (filter list? lst)))) Problem 16 There are many ways to do this problem. One is to assume that the simplest input that makes sense is a number. In which case, all we need to do is pop off the operator -- the car of EXPR -- and map ARITH-EVAL on the cdr. (define (arith-eval expr) (if (number? expr) expr (apply (procedurize (car expr)) (map arith-eval (cdr expr))))) In a simple case such as (arith-eval '(+ 1 2 3 4)) the cdr will consist of numbers, in which case ARITH-EVAL will serve as the identity function when its mapped. In a more complicated case, such as (arith-eval '(+ (- 3 4) (* 3 4))) we will trust the recursion and assume that ARITH-EVAL will simplify any nested arithmetic expression and return to us just a list of numbers. Either way, we trust that the line (map arith-eval (cdr expr)) always returns a list of numbers. Then, we need only apply the PROCEDURIZEd operator to this list of numbers. Here is a recursive solution. (define (arith-eval expr) (if (number? expr) expr (apply-operator (procedurize (car expr)) (cdr expr)))) (define (apply-operator func args) (if (null? (cdr args)) (arith-eval (car args)) (func (arith-eval (car args)) (apply-operator func (cdr args))))) Well, actually its mutually-recursive. That means you've got two functions calling each other. The difference is that APPLY-OPERATOR takes a function and a list of its arguments. In the simple case, the argument list will be all numbers, like (1 2 3), in which case APPLY-OPERATOR simply applies FUNC to two of them at a time. In the complicated case when the arguments contain subexpressions, we use a call to ARITH-EVAL to break them down to numbers. Problem 17 (define (count-up n) (accumulate append '() (map (lambda (upper) (enumerate-interval 1 upper)) (enumerate-interval 1 n)))) The easiest way to get this solution is work from the bottom up. Let's say we call COUNT-UP with 4. We then want to get (1 1 2 1 2 3 1 2 3 4). First, we enumerate, yielding (1 2 3 4). Each of these numbers is the upper-bound of the sub-enumerations in the result we want. We need to introduce a bit of terminology here. A sequence of strictly increasing or strictly decreasing numbers is called a "run." The list (1 1 2 1 2 3 1 2 3 4) contains 4 ascending runs: (1), (1 2), (1 2 3) and (1 2 3 4). The enumeration (1 2 3 4) contains the upper-bounds of these runs. Thus, for every number N in the enumeration (1 2 3 4), we need to enumerate from 1 to N, yielding ((1) (1 2) (1 2 3) (1 2 3 4)). All that's left is to flatten the result. APPLYing or ACCUMULATing APPEND does that.