sicp-ex-2.29



<< Previous exercise (2.28) | Index | Next exercise (2.30) >>


2DSharp

Making the constructors and selectors first for building the bigger solution on.

Version one using lists

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

Version two using cons instead of lists

 (define (make-mobile left right) 
   (cons left right)) 
  
 (define (left-branch mobile) 
   (car mobile)) 
 (define (right-branch mobile) 
   ;; Have to use cdr at this point  
   (cdr mobile))  
  
 (define (make-branch length structure) 
   (cons length structure)) 
  
 (define (branch-length branch) 
   (car branch)) 
 (define (branch-structure branch) 
   (cdr branch)) 

Rest of the problem

 ;; Finding the total weight of a binary mobile 
 ;; Using wishful thinking to recurse the addition of left-branch and right-branch mobiles 
  
 (define (total-weight mobile) 
   (cond ((null? mobile) 0) 
         ((not (pair? mobile)) mobile) 
         (else (+ (total-weight (branch-structure (left-branch mobile))) 
                  (total-weight (branch-structure (right-branch mobile))))))) 
  
 ;; Test  
 (define a (make-mobile (make-branch 2 3) (make-branch 2 3))) 
 (total-weight a) ;; 6 
  
 (define (torque branch) 
   (* (branch-length branch) (total-weight (branch-structure branch)))) 
  
 ;; Finally to check if the torques of both sides are equal 
 ;; And if the sub-mobiles are balanced using recursion 
  
 (define (balanced? mobile) 
   (if (not (pair? mobile)) 
       true 
       (and (= (torque (left-branch mobile)) (torque (right-branch mobile))) 
            (balanced? (branch-structure (left-branch mobile))) 
            (balanced? (branch-structure (right-branch mobile)))))) 
  
 ;; Test 
  
 (define d (make-mobile (make-branch 10 a) (make-branch 12 5))) 
 ;; Looks like: ((10 ((2 3) (2 3))) (12 5)) 
  
 (balanced? d) ;; #t 

The test cases were used from Bill the Lizard's blog on SICP


Rather Iffy

Use the same recursion over the construction of the mobile for defining the function 'total-weight' as; well as the predicate 'balanced?'. Take advantage of the fact that a variable has no type. The variab;le 'm' can in different calls take as a value a mobile, a branch or a number or empty list.

 ; Definition of constructors and selectors 
  
 (define (make-mobile left right) 
   (list left right)) 
 (define (left-branch mobile) 
   (car mobile)) 
 (define (right-branch mobile) 
   (car (cdr mobile))) 
  
 (define (make-branch length structure) 
   (list length structure)) 
 (define (branch-length branch) 
   (car branch)) 
 (define (branch-structure branch) 
   (car (cdr branch))) 
  
 ;; Redefinition of constructors and selectors 
  
 (define (make-mobile left right) 
   (cons left right)) 
 (define (left-branch mobile) 
   (car mobile)) 
 (define (right-branch mobile) 
   (cdr mobile)) 
  
 (define (make-branch length structure) 
   (cons length structure)) 
 (define (branch-length branch) 
   (car branch)) 
 (define (branch-structure branch) 
   (cdr branch)) 
  
  
 (define (total-weight m) 
   (cond ((null? m) 0) 
         ((not (pair? m)) m) 
         (else (+ (total-weight (branch-structure (left-branch  m))) 
                  (total-weight (branch-structure (right-branch m))))))) 
  
 (define m1 (make-mobile 
             (make-branch 4 6) 
             (make-branch 5 
                          (make-mobile 
                           (make-branch 3 7) 
                           (make-branch 9 8))))) 
  
 ;;          4  |  5 
 ;;        +----+-----+ 
 ;;        6        3 |     9 
 ;;               +---+---------+ 
 ;;               7             8 
  
 ;  (total-weight m1) 
 ;  Value: 21 
  
 (define (balanced? m) 
   (cond ((null? m) #t) 
         ((not (pair? m)) #t) 
         (else 
          (and (= (* (branch-length (left-branch m)) 
                     (total-weight (branch-structure (left-branch m)))) 
                  (* (branch-length (right-branch m)) 
                     (total-weight (branch-structure (right-branch m))))) 
               (balanced? (branch-structure (left-branch   m))) 
               (balanced? (branch-structure (right-branch  m))))))) 
  
 (define m2 (make-mobile 
             (make-branch 4 6) 
             (make-branch 2 
                          (make-mobile 
                           (make-branch 5 8) 
                           (make-branch 10 4))))) 
  
 ;;          4  | 2 
 ;;        +----+--+ 
 ;;        6    5  |    10 
 ;;          +-----+----------+ 
 ;;          8                4 
  
 (balanced? m2) 
 ;Value: #t 
 (balanced? m1) 
 ;Value: #f