Chapter 2, Building Abstractions with Data
Section - 2.2 - Hierarchical Data and the Closure Property
Exercise 2.29
(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#lang sicp
(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))
)
(b)
1
2
3
4
5
6
7
8
9
10
(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)))
)
)
)
)
Example/Test:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
> (define mob
(make-mobile
(make-branch
100
(make-mobile
(make-branch 100 1)
(make-branch
100
(make-mobile
(make-branch 100 2)
(make-branch 100 3)
)
)
)
)
(make-branch
100
(make-mobile
(make-branch
100
(make-mobile
(make-branch 100 4)
(make-branch 100 5)
)
)
(make-branch 100 6)
)
)
)
)
> (total-weight mob)
21
> (total-weight '())
0
(c)
I attempted in writing procedure that visits each branch of the mobile only once.
To do that a procedure chk-balance is written which returns weight of the mobile if mobile is balanced else it returns a negative
number. As can be seen in code this helps in avoiding multiple visits to each branch.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(define (balanced? m)
(define (chk-balance mobile)
(cond ((null? mobile) 0)
((not (pair? mobile)) mobile)
(else
(let (
(left-wt (chk-balance (branch-structure (left-branch mobile))))
(right-wt (chk-balance (branch-structure (right-branch mobile))))
)
(if (and
(>= left-wt 0)
(>= right-wt 0)
(=
(* left-wt (branch-length (left-branch mobile)))
(* right-wt (branch-length (right-branch mobile)))
)
)
(+ left-wt right-wt)
-1
)
)
)
)
)
(>= (chk-balance m) 0)
)
Example/Test:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
> (define mob
(make-mobile
(make-branch
100
(make-mobile
(make-branch 100 1)
(make-branch 100 (make-mobile (make-branch 100 2) (make-branch 100 3)))
)
)
(make-branch
100
(make-mobile
(make-branch 100 (make-mobile (make-branch 100 4) (make-branch 100 5)))
(make-branch 100 6)
)
)
)
)
> (balanced? mob)
#f
> (define mob
(make-mobile
(make-branch
100
(make-mobile
(make-branch 100 16)
(make-branch 100 (make-mobile (make-branch 100 8) (make-branch 100 8)))
)
)
(make-branch
100
(make-mobile
(make-branch 100 (make-mobile (make-branch 100 8) (make-branch 100 8)))
(make-branch 100 16)
)
)
)
)
> (balanced? mob)
#t
(d)
The modified constructors will cause changes only in selectors right-branch and branch-structure.