SICP 연습문제 2.29 친절한 풀이

문제

왼쪽과 오른쪽에 팔이 하나씩 달린 모빌^{binary mobile}이 있다고 하자. 두 팔 모빌은 다음과 같이 가지^막대기 두 개를 (여기서는, list를 써서) 합친 데이터로 나타낼 수 있다.

(define (make-mobile left right)
  (list left right))

또, 가지는 length(반드시 수여야 한다.)와 structure로 짜맞출 수 있다. 여기서 structure는 (추의 무게를 나타내는) 수나 다른 모빌일 수 있다.

(define (make-branch length structure)
  (list length structure))

a. 모빌에서 가지를 골라내는 left-branch와 right-brancgh를 만들어라. 또 가지의 구성 요소를 골라내는 branch-length와 branch-structure도 만들어라.

b. 앞에서 만든 고르개^selector를 써서, 모빌의 전체 무게를 구하는 프로시저 total-weight를 정의해 보라.

c. 모빌이 균형잡힌^balanced상태가 되려면 왼쪽 맨 윗가지의 돌림힘^{토크,torque}과, 오른쪽 맨 윗가지의 돌림힘이 같아야 하고(다시말해, 왼쪽 막대 길이와 그 막대에 매달린 전체 추를 곱한 값이 오른쪽 막대에서 구한 값과 같아야 하고), 가지마다 매달린 모든 부분 모빌도 마찬가지로 균형 잡힌 상태여야 한다. 두 팔 모빌이 균형 잡혔는지 알아보는 술어 프로시저를 짜라.

d. 짜맞추개^constructor를 다음처럼 다시 정의하여 모빌 표현을 바꿨다고 하자.

(define (make-mobile left right)
  (cons left right))
  
(define (make-branch length structure)
  (cons length structure))

위와 같이 짜맞추개를 고쳤다면, 지금까지 짠 프로그램은 또 얼마나 손봐야 하는가?

문제로 부터 얻은 것

리스트나 쌍으로 구성된 데이터를 다루는 테크닉이 좀 더 좋아진 것 같습니다.

문제풀이

문제 풀이에 사용할 테스트 모빌 m1, m2는 다음과 같습니다.

;;          4  |  5 
;;        +----+-----+ 
;;        6        3 |     9 
;;               +---+---------+ 
;;               7             8 
(define m1 (make-mobile 
            (make-branch 4 6) 
            (make-branch 5 
                         (make-mobile 
                          (make-branch 3 7) 
                          (make-branch 9 8)))))

;;          4  | 2 
;;        +----+--+ 
;;        6    5  |    10 
;;          +-----+----------+ 
;;          8                4 
(define m2 (make-mobile 
            (make-branch 4 6) 
            (make-branch 2 
                         (make-mobile 
                          (make-branch 5 8) 
                          (make-branch 10 4)))))

a. 고르개 만들기

모빌과 가지의 구현이 cons가 아니라 list임에 주의해야 합니다. 두번째 원소를 꺼낼 때에는 car과 cdr을 둘 다 사용해 주어야 합니다.

(define (left-branch x)
  (car x))

(define (right-branch x)
  (car (cdr x)))

(define (branch-length x)
  (car x))

(define (branch-structure x)
  (car (cdr x)))

b. 모빌의 무게를 구하는 프로시저

모빌의 무게를 구하는 것은 모든 가지의 끝에 묶여있는 branch-structure의 무게를 더하는 것과 같습니다. 이점을 유의하여 프로시저를 만들어 보았습니다. 프로시저의 핵심 동작 원리는 다음과 같습니다. 모빌을 탐색하면서 가지의 끝에 도달할 때마다, 만약 새로운 모빌이 가지 끝에 매여 있다면, 양쪽의 무게를 더하는 것입니다.

(+ (mobile-weight (branch-structure (left-branch x)))
   (mobile-weight (branch-structure (right-branch x))))

구현한 프로시저는 아래와 같습니다.

(define (mobile-weight x)
  (cond ((null? x) 0)
        ((pair? x) (+ (mobile-weight (branch-structure (left-branch x)))
                      (mobile-weight (branch-structure (right-branch x)))))
        (else x)))

c. 모빌의 균형을 검사하는 프로시저

모빌의 균형을 검사하는 프로시저의 핵심 동작 원리는 다음과 같습니다.

1. 모빌의 왼쪽 가지와 오른쪽 가지 사이의 균형을 검사한다. (토크의 크기가 같은지 확인한다.)
2. 모빌의 왼쪽 가지 끝에 매인 모빌의 균형을 검사한다.
3. 모빌의 오른쪽 가지 끝네 매인 모빌의 균형을 검사한다.

위의 아이디어로 구현한 프로시저는 아래와 같습니다.

(define (balanced? x)
  (define (torque ward mobile)
    (* (branch-length (ward x))
       (mobile-weight (branch-structure (ward x)))))
  
  (cond ((null? x) #t)
        ((pair? x) (and (= (torque left-branch x)
                           (torque right-branch x))
                        (balanced? (branch-structure (left-branch x)))
                        (balanced? (branch-structure (right-branch x)))))
        (else #t)))

d. 새로운 짜맞추개

기존의 list로 구현한 모빌과 가지를 cons로 바꾼 것 뿐입니다. 추상화 장벽 덕분에 데이터의 고르개^selector만 수정해 준다면, left-branch나 branch-structure를 사용하는 프로시저에서는 신경쓸 것이 없습니다.

(define (left-branch x)
  (car x))

(define (right-branch x)
  (cdr x))

(define (branch-length x)
  (car x))

(define (branch-structure x)
  (cdr x))

e. 프로시저 검사

지금까지 만든 프로시저들을 m1, m2에 적용해서 예상한 결과가 나오는지 확인해 보겠습니다.

(mobile-weight m1)
(mobile-weight m2)
(balanced? m1)
(balanced? m2)

읽어주셔서 감사합니다.