## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.29

## Contents |

## Problem

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

## Problem, part A

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.

## Solution, part A

This part is easy. All of the selectors can be built using list primitives:

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

Test:

(define mobile1 (make-mobile (make-branch 2 4) (make-branch 3 (make-mobile (make-branch 2 1) (make-branch 4 2))))) mobile1

*Output:*

`
`

((2 4) (3 ((2 1) (4 2))))

(left-branch mobile1)

*Output:*

`
`

(2 4)

(right-branch mobile1)

*Output:*

`
`

(3 ((2 1) (4 2)))

(branch-length (left-branch mobile1))

*Output:*

`
`

2

(branch-structure (left-branch mobile1))

*Output:*

`
`

4

(branch-length (right-branch mobile1))

*Output:*

`
`

3

(branch-structure (right-branch mobile1))

*Output:*

`
`

((2 1) (4 2))

(left-branch (branch-structure (right-branch mobile1)))

*Output:*

`
`

(2 1)

(right-branch (branch-structure (right-branch mobile1)))

*Output:*

`
`

(4 2)

(branch-length (left-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

2

(branch-structure (left-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

1

(branch-length (right-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

4

(branch-structure (right-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

2

## Problem, part B

Using your selectors, define a procedure `total-weight` that
returns the total weight of a mobile.

## Solution, part B

A branch structure may be either a simple weight (a number) or another mobile, so we need a way to distinguish the two cases.

Because we're implementing these procedures ourselves, we happen to
know that mobiles are represented as lists. Each time we need to
determine the type of a branch structure, we could tell the user to use the `pair?`
primitive, but it's not a good idea -- it exposes the actual
representation of mobiles, which is supposed to be an internal
detail of our design, to users of our abstraction of mobiles.

The description of our system says simply that a branch structure
may be either a number or a mobile. It does not specify how a
mobile is represented, and that's a good thing, because it gives us
the freedom to change that representation later. Requiring our
users to determine the type of branch structure with `pair?` may cause
problems if we want to change the representation of mobiles later.
And of course, we are users of the code, too, so we should limit the
number of places in our own code where we make assumptions about our
implementation to provide ourselves the same flexibility.

`total-weight` needs to know what type of branch structure it's
dealing with, so now's a good time to define a procedure that can
make the determination in an abstract way. Procedure `mobile?`
becomes part of the conventional interface for our mobile
abstraction.

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

Test:

(mobile? mobile1)

*Output:*

`
`

#t

(mobile? (branch-structure (left-branch mobile1)))

*Output:*

`
`

#f

(mobile? (branch-structure (right-branch mobile1)))

*Output:*

`
`

#t

(branch-weight (left-branch mobile1))

*Output:*

`
`

4

(branch-weight (right-branch mobile1))

*Output:*

`
`

3

(total-weight mobile1)

*Output:*

`
`

7

(total-weight (branch-structure (right-branch mobile1)))

*Output:*

`
`

3

## Problem, part C

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.

## Solution, part C

Here's one possible implementation:

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

Test:

(torque (left-branch mobile1))

*Output:*

`
`

8

(torque (right-branch mobile1))

*Output:*

`
`

9

(balanced? mobile1)

*Output:*

`
`

#f

(define mobile2 (make-mobile (make-branch 2 4) (make-branch 8 1))) (balanced? mobile2)

*Output:*

`
`

#t

## Problem, part D

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?

## Solution, part D

We have to change the selectors, since those are dependent on the representation of mobiles and branches:

(define (left-branch mobile) (car mobile)) (define (right-branch mobile) (cdr mobile)) (define (branch-length branch) (car branch)) (define (branch-structure branch) (cdr branch))

Test:

(define mobile1 (make-mobile (make-branch 2 4) (make-branch 3 (make-mobile (make-branch 2 1) (make-branch 4 2))))) mobile1

*Output:*

`
`

((2 . 4) 3 (2 . 1) 4 . 2)

This "dot-notation" is unfamiliar, and we'll learn about it later in
the text, but we can ignore it for the purposes of this exercise.

(left-branch mobile1)

*Output:*

`
`

(2 . 4)

(right-branch mobile1)

*Output:*

`
`

(3 (2 . 1) 4 . 2)

(branch-length (left-branch mobile1))

*Output:*

`
`

2

(branch-structure (left-branch mobile1))

*Output:*

`
`

4

(branch-length (right-branch mobile1))

*Output:*

`
`

3

(branch-structure (right-branch mobile1))

*Output:*

`
`

((2 . 1) 4 . 2)

(left-branch (branch-structure (right-branch mobile1)))

*Output:*

`
`

(2 . 1)

(right-branch (branch-structure (right-branch mobile1)))

*Output:*

`
`

(4 . 2)

(branch-length (left-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

2

(branch-structure (left-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

1

(branch-length (right-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

4

(branch-structure (right-branch (branch-structure (right-branch mobile1))))

*Output:*

`
`

2

Despite the unfamiliar notation of the non-number representations,
our new selectors appear to be working. What else do we need to
change?

The only other procedure we defined that depends on the
representation of the mobile is the `mobile?` predicate. It uses the
`pair?` primitive to distinguish mobile branch structures from simple
weight (number) branch structures. In the new system, mobiles are
still represented as pairs, since they're constructed via `cons`; and
weights are still represented by numbers, so the `mobile?` predicate
we wrote should continue to function properly. Let's check.

(mobile? mobile1)

*Output:*

`
`

#t

(mobile? (branch-structure (left-branch mobile1)))

*Output:*

`
`

#f

(mobile? (branch-structure (right-branch mobile1)))

*Output:*

`
`

#t

(mobile? (branch-structure (left-branch (branch-structure (right-branch mobile1)))))

*Output:*

`
`

#f

Looks good. Test the rest of our code to make sure everything else
is working properly.

(branch-weight (left-branch mobile1))

*Output:*

`
`

4

(branch-weight (right-branch mobile1))

*Output:*

`
`

3

(total-weight mobile1)

*Output:*

`
`

7

(total-weight (branch-structure (right-branch mobile1)))

*Output:*

`
`

3

(torque (left-branch mobile1))

*Output:*

`
`

8

(torque (right-branch mobile1))

*Output:*

`
`

9

(balanced? mobile1)

*Output:*

`
`

#f

(define mobile2 (make-mobile (make-branch 2 4) (make-branch 8 1))) (balanced? mobile2)

*Output:*

`
`

#t

## Credits

Wu Zhe provided a proper recursive definition of the `balanced?` procedure. My original procedure only checked that the weights of the left and right branches are equal, but the exercise clearly states that a mobile is only "balanced" when all of the submobiles are balanced, too. Thanks!