SICP Exercise Solutions - Chapter 2

Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:
Solution:

(define (make-point x y)
  (cons x y))

(define (x-point p)
  (car p))

(define (y-point p)
  (cdr p))

(define (make-segment p1 p2)
  (cons p1 p2))

(define (start-segment s)
  (car s))

(define (end-segment s)
  (cdr s))

(define (midpoint-segment ls)
  (make-point 
               (avg (x-point (start-segment ls)) (x-point (end-segment ls)))
               (avg (y-point (start-segment ls)) (y-point (end-segment ls)))
               ))

(define (avg x y)
  (/ (+ x y) 2))

;Test Data
(define p1 (make-point 4 6))
(define p2 (make-point 8 18))
(define ls (make-segment p1 p2))
(midpoint-segment ls)
;6 12

Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))

Solution:

(define (rev items)
  (define (helper items rl)
    (if (null? items) rl
        (helper (cdr items) (cons (car items) rl))))
  (helper items null))

(define (deep-rev items)
  (define (helper ritems)
  (if (null? ritems)
      null
      (cons (if (not (pair? (car ritems))) (car ritems)(rev(car ritems))) (helper (cdr ritems)))))
  (helper (rev items)))

Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)

Solution:

(define (fringe items)
  (cond ((null? items) null)
        (else (append (if (not (pair? (car items))) (list (car items)) (car items)) (fringe (cdr items))))))

(define (deep-fringe items)
  (if (not (exists-pair? items))
      items
      (deep-fringe (fringe items))))

(define (exists-pair? items)
  (cond ((null? items) #f)
        ((pair? (car items)) #t)
        (else (exists-pair? (cdr items)))))

Exercise 2.29. 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))

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.
b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
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:
a)

(define (make-branch len st)
  (list len st))
(define (make-mobile lb rb)
  (list lb rb))
(define (left-branch m)
  (car m))
(define (right-branch m)
  (car (cdr m)))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (car (cdr b)))

b)

(define (mobile? m)
  (pair? m))

(define (total-weight m)
  (cond ((null? m) 0)
        ((not (mobile? m)) m)
        (else (+ (total-weight (branch-structure (left-branch m)))
                 (total-weight (branch-structure (right-branch m)))))))
;Test
(define lb3 (make-branch 2 1))
(define rb3 (make-branch 1 2))
(define mb3 (make-mobile lb3 rb3))
(define lb2 (make-branch 3 mb3))
(define rb2 (make-branch 9 1))
(define mb2 (make-mobile lb2 rb2))
(define lb1 (make-branch 4 mb2))
(define rb1 (make-branch 8 2))
(define mb1 (make-mobile lb1 rb1))

(total-weight mb3)
(total-weight mb2)
(total-weight mb1)

d)

(define (make-branch len st)
  (cons len st))
(define (make-mobile lb rb)
  (cons lb rb))
(define (left-branch m)
  (car m))
(define (right-branch m)
  (cdr m))
(define (branch-length b)
  (car b))
(define (branch-structure b)
  (cdr b))