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

From Drewiki
Jump to: navigation, search

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!

Personal tools