Problem 2.29

Bottom line: Your code needs to work, regardless of the how the abstraction for mobiles and branches is implemented. You are not guaranteed a particular implementation. You are just guaranteed that the abstraction itself will work. So, if the underlying implementation were changed to:

(define (make-mobile lb rb)
  (lambda (msg)
    (cond ((= msg 0) lb)
          ((= msg 1) rb))))
(define (left-branch mobile)
  (mobile 0))
(define (right-branch mobile)
  (mobile 1))

(define (make-branch l s)
  (lambda (msg)
    (cond ((eq? msg 'length) l)
          ((eq? msg 'structure) s))))
(define (len branch)
  (branch 'length))
(define (struct branch)
  (branch 'structure))

(define weight? number?)
(define (mobile? structure)
  (not (weight? structure)))

... your code still needs to work! And it cannot possibly work if you have used list and pair selectors and predicates such as car, cdr, pair?, and list? You need to be using make-mobile, left-branch, right-branch, make-branch, len, struct, weight?, and mobile?

Here is a solution; there are other ways to go about this problem that are equally good. I offer this version as total-weight and branch-weight are mutually recursive and balanced? can be written without cond or if. I think those features are worth studying.

(define (total-weight structure)
  (cond ((weight? structure) structure)
        (else (+ (branch-weight (left-branch structure))
                 (branch-weight (right-branch structure))))))
(define (branch-weight branch)
  (total-weight (struct branch)))

(define (torque branch)
  (* (len branch) (total-weight (struct branch))))

(define (balanced? structure)
  (or (weight? structure)
      (and (= (torque (left-branch structure)) (torque (right-branch structure)))
           (balanced? (struct (left-branch structure)))
           (balanced? (struct (right-branch structure))))))

Problem 2.32

One of the most elegant pieces of code I've ever seen...

(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (set) (cons (car s) set)) rest)))))

I think it is helpful to note the following:

> (subsets '())
(())

is given in the original code. This means that if the call

> (subsets '(A))
(() (A))

is performed, the variable rest is going to be '(()). The only way to get the set (A) into the solution is by cons-ing it onto all of the lists of rest as (cons 'A '()) is the list of A.

Problem 2.33

Probably the best way to approach this is to understand that the first input to accumulate is a function that takes two inputs. The first input to that function will be the first element of the sequence (in the form of a list) and the second input will be the rest of the list.

The other thing worth noting is we know what map, append, and length are supposed to do in Scheme. So, whatever goes into the given blanks, we can look at what happens with an empty list for the sequence and a one-element list from the sequence and try to generalize.

Remember also that if e is an element and l is a list, (cons e l) returns a list with e as the car and l as the cdr, which has the effect of placing e at the beginning of l.

Finally remember that if you need to diagram an N-element list, it will have precisely N pairs, with the last cdr being an empty list. Sometimes such diagrams can be helpful in understanding how lists are constructed recursively.

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

Problem 2.35

(define (leaf? t) (not (pair? t)))
(define (count-leaves t)
  (accumulate + 0 (map (lambda (node)
                         (if (leaf? node)
                             1
                             (count-leaves node)))
                       t)))