SICP 2.29: Binary Mobiles

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.29 defines a binary mobile as a structure consisting of a left branch and a right branch, each of which is a rod of a certain length, from which hangs either a weight or another binary mobile.



The following constructors are provided, giving us a representation of binary mobiles held together with the list procedure:

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

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

Our first task is to 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.

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

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

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

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

Next we need to define a procedure total-weight that returns the weight of an entire mobile. The total weight of a mobile is just the sum of the left branch and the right branch. The weight of a branch is defined recursively if the branch is itself a mobile, or just returned if the branch holds a single weight.

(define (branch-weight branch)
   (if (pair? (branch-structure branch))
       (total-weight (branch-structure branch))
       (branch-structure branch)))

(define (total-weight mobile)
   (+ (branch-weight (left-branch mobile))
      (branch-weight (right-branch mobile))))

Note how branch-weight and total-weight call each other recursively. The recursion reaches a base case when a weight (leaf node) is encountered.

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 from the right side) and if each of the sub-mobiles hanging off its branches is balanced. Our next task is to design a predicate procedure that tests whether a binary mobile is balanced.

First we'll need a simple procedure for calculating the torque of a branch from the definition above.

(define (branch-torque branch)
   (* (branch-length branch)
      (branch-weight branch)))

Now we can use the same mutual recursion pattern we used to find the total weight of a mobile to write procedures to determine if a mobile and its branches are balanced.

(define (branch-balanced? branch)
   (if (pair? (branch-structure branch))
       (balanced? (branch-structure branch))
       true))

(define (balanced? mobile)
   (and (= (branch-torque (left-branch mobile))
           (branch-torque (right-branch mobile)))
        (branch-balanced? (left-branch mobile))
        (branch-balanced? (right-branch mobile))))

Before we go on to the last step, this would be a good spot to test what we've done so far. The simplest mobile we can make has two branches with simple weights. Let's define two of those (one balanced and one unbalanced) and run a few simple tests.

> (define a (make-mobile (make-branch 2 3) (make-branch 2 3)))
> a
((2 3) (2 3))
> (define b (make-mobile (make-branch 2 3) (make-branch 4 5)))
> b
((2 3) (4 5))
> (total-weight a)
6
> (total-weight b)
8
> (balanced? a)
#t
> (balanced? b)
#f

Now we can create a more complicated mobile by combining the two above.

> (define c (make-mobile (make-branch 5 a) (make-branch 3 b)))
> c
((5 ((2 3) (2 3))) (3 ((2 3) (4 5))))
> (total-weight c)
14
> (balanced? c)
#f

For one last test case, let's try to make a balanced mobile that has mobile a above on a rod of length 10 on the left branch, and a weight of 5 on the right branch. What would the length of the rod on the right need to be in order to balance the entire mobile?




The torque on the left is the total weight of mobile a multiplied by the length, so 6 x 10 gives us a torque of 60. In order to balance the mobile we need the same torque on the right. Since the right side weight is only 5, we'd need a rod of length 60 / 5 = 12 on the right for the mobile to be balanced.

> (define d (make-mobile (make-branch 10 a) (make-branch 12 5)))
> d
((10 ((2 3) (2 3))) (12 5))
> (balanced? d)
#t

Finally, we're asked how much we'd need to change our programs if the original constructors were changed to the following:

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

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

The only difference is the use of cons to glue the pieces of the mobile and its branches together instead of list. Since only the constructor and accessor procedures know anything about the underlying structure of a mobile, only the accessors would need to change. In this case only the right-branch and branch-structure procedures are affected.

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

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

This is a great benefit of layering abstractions.

You can test out this new implementation using the same mobiles we defined above.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.