SICP Exercise 2.29

2022-01-09

Question

A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

(define (make-mobile left right)
  (list left right))

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

(define (make-branch length structure)
  (list length structure))

Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.
Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the sub-mobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.
Suppose we change the representation of mobiles so that the constructors are
```
   (define (make-mobile left right)
     (cons left right))

   (define (make-branch length structure)
     (cons length structure))
```
How much do you need to change your programs to convert to the new representation?

Answer

For testing my code, I am using two simple test mobiles (one unbalanced, one balanced) with the following shapes, lengths and weights (in circles):

Here’s the code for the first three exercises:

; 1
(define (left-branch m) (car m))
(define (right-branch m) (cadr m))
(define (branch-length b) (car b))
(define (branch-structure b) (cadr b))

; 2
(define (total-weight m)
  (if (not (pair? m))
      m
      (let ((bsl (branch-structure (left-branch m)))
            (bsr (branch-structure (right-branch m))))
        (cond ((and (not (pair? bsl)) (not (pair? bsr))) (+ bsl bsr))
              ((not (pair? bsl)) (+ bsl (total-weight bsr)))
              ((not (pair? bsr)) (+ bsr (total-weight bsl)))
              (else (+ (total-weight bsl) (total-weight bsr)))))))

; 3
(define (torque b)
  (* (branch-length b) (total-weight (branch-structure b))))
(define (torques-equal? b1 b2)
  (equal? (torque b1) (torque b2)))

(define (balanced? m)
  (if (or (null? m) (not (pair? m)))
      #t
      (and (torques-equal? (left-branch m) (right-branch m))
            (balanced? (branch-structure (left-branch m)))
            (balanced? (branch-structure (right-branch m))))))

Let’s test it with the two mobiles described above:

; testing
(define m_unbalanced (make-mobile (make-branch 1 2)
                                  (make-branch 1 (make-mobile (make-branch 0.5 3)
                                                              (make-branch 2 4)))))
(define m_balanced (make-mobile (make-branch 1 2)
                                (make-branch 1 (make-mobile (make-branch 1 1)
                                                            (make-branch 1 1)))))

(total-weight m_unbalanced)
(total-weight m_balanced)
(balanced? m_unbalanced)
(balanced? m_balanced)

The results are as expected:

9
4
#f
#t

As for exercise number 4, the only changes that need to be made are in right-branch and in branch-structure, in which cadr needs to be changed to cdr. This is necessary since, by using cons rather than list to construct the pair, the second element (the cdr) is now also a single value, whereas before it was a list containing a single value, so we had to use cadr. See the following snippet for comparison:

(cdr (list 1 2))
(cdr (cons 1 2))
(cadr (list 1 2))

Results:

(2)
2
2

So the new implementation of exercise 1 would look like the following:

(define (left-branch m) (car m))
(define (right-branch m) (cdr m))
(define (branch-length b) (car b))
(define (branch-structure b) (cdr b))