SICP Exercise 2.29: Binary Mobiles

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))

1. 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.
2. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
3. 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 submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.
4. 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?

a. Writing the Selectors

Both mobiles and mobile branches are stored as two-element lists. Now we know from at least one previous exercise that we can extract the first element of a list by using car and the second element by using cadr. This means that our selectors can simply use these operations to extract the appropriate elements from the lists:

(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (cadr mobile))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (cadr branch))

Let's give ourselves some mobiles to test with:

(define mobile1
  (make-mobile (make-branch 10 1)
               (make-branch 2 5)))

(define mobile2
  (make-mobile (make-branch 10 1)
               (make-branch 2 (make-mobile (make-branch 4 1)
                                           (make-branch 1 4)))))

(define mobile3
  (make-mobile (make-branch 9 1)
               (make-branch 2 4)))

...and check these selectors work:

> (left-branch mobile1)
'(10 1)
>  (right-branch mobile1)
'(2 5)
>  (left-branch mobile2)
'(10 1)
>  (right-branch mobile2)
'(2 ((4 1) (1 4)))
>  (branch-length (left-branch mobile1))
10
>  (branch-structure (left-branch mobile1))
1
>  (branch-length (right-branch mobile2))
2
> (branch-structure (right-branch mobile2))
'((4 1) (1 4))

b. Getting the Total Weight

To get the total weight of a mobile we need to navigate the entire tree, find all the leaf branches (i.e. where their structure is not a pair, but is instead a number) and sum their weights. This can be achieved via a recursive operation: to get the weight of any mobile we need to get the sum of the two branches' weights; to get the weight of a branch we need to check whether the structure is a mobile (i.e. a pair) or not - if it is then we need to get the weight of that mobile, otherwise the structure is its weight.

We'll introduce an inner procedure, branch-weight which gets the weight of a branch. It will evaluate to the structure's value if it's not a pair, or call total-weight with the structure to get the weight of the contained mobile. We'll also assume, as we've been doing for most exercises so far, that the mobile is correctly formed:

(define (total-weight mobile)
  (define (branch-weight branch)
    (let ((structure (branch-structure branch)))
      (if (pair? structure)
          (total-weight structure)
          structure)))
  (+ (branch-weight (left-branch mobile))
      (branch-weight (right-branch mobile))))

And let's check it works using the mobiles from above:

> (total-weight mobile1)
6
> (total-weight mobile2)
6
> (total-weight mobile3)
5

c. Testing for Balanced Mobiles

Just as well we wrote that total-weight procedure above. We can use that to calculate the torque of a branch by multiplying the length of the branch by the total weight of the branch. Then we can test whether a particular level within a mobile is balanced by comparing the torque of the two branches. But before we can do that, we need to note that a branch doesn't necessarily contain a mobile - it's structure could just be a numeric weight. Let's modify total weight so that it'll accept any valid structure, rather than just valid mobiles:

(define (total-weight mobile)
  (define (branch-weight branch)
    (let ((structure (branch-structure branch)))
      (if (not (pair? structure))
          structure
          (total-weight structure))))
  (if (pair? mobile)
      (+ (branch-weight (left-branch mobile))
         (branch-weight (right-branch mobile)))
      mobile))

Now obviously we'll need to do this comparison of branch torques all the way down the mobile's structure: the branches of each sub-mobile must also be balanced, not just the root mobile. To help us we'll introduce an inner procedure, torque, that calculates the torque of a branch. Then we can write our predicate, balanced?, and define its main body such that it checks that the two branches have the same torque and that the structures held within the two branches are also balanced (by recursively calling balanced? for those structures). Of course this means that balanced? has to be able to deal with structure values that are numeric values rather than mobiles. We can cope with this by having balanced? check whether or not it's dealing with a pair. If it is then it processes it as a mobile; if it isn't then it can just evaluate to true - a single hanging weight is inherently balanced (at least for the purposes of this exercise anyway).

Here's the implementation:

(define (balanced? mobile)
  (define (torque branch)
    (* (branch-length branch)
       (total-weight (branch-structure branch))))
  (if (pair? mobile)
      (let ((left (left-branch mobile))
            (right (right-branch mobile)))
        (and (= (torque left) (torque right))
             (balanced? (branch-structure left))
             (balanced? (branch-structure right))))
      #t))

Let's check our test mobiles:

> (balanced? mobile1)
#t
> (balanced? mobile2)
#t
> (balanced? mobile3)
#f

d. Using Pairs Instead of Lists

For the final part of the exercise the constructors are changed to produce simple pairs of values rather than two-element lists. Now as in our total-weight and balanced? procedures we only ever access mobile and branch components via the selectors our changes should be restricted to these alone. Further, note that the mechanism for accessing the head of a list is the same as that for accessing the first element of a pair. I.e. car, as a list is just a chain of pairs with the n^th element of the list held as the first element of the n^th pair. As a result we should only have to change the selectors which extract the second elements of the mobile and branch structures, namely right-branch and branch-structure, and as we're dealing with pairs, we simply replace cadr with cdr:

(define (right-branch mobile)
  (cdr mobile))

(define (branch-structure branch)
  (cdr branch))

Let's put this to the test:

> (left-branch mobile1)
'(10 . 1)
> (right-branch mobile1)
'(2 . 5)
> (left-branch mobile2)
'(10 . 1)
> (right-branch mobile2)
'(2 (4 . 1) 1 . 4)
> (branch-length (left-branch mobile1))
10
> (branch-structure (left-branch mobile1))
1
> (branch-length (right-branch mobile2))
2
> (branch-structure (right-branch mobile2))
'((4 . 1) 1 . 4)
> (total-weight mobile1)
6
> (total-weight mobile2)
6
> (total-weight mobile3)
5
> (balanced? mobile1)
#t
> (balanced? mobile2)
#t
> (balanced? mobile3)
#f