리스트 계층 구조를 활용해 tree 자료구조를 표현할 수 있다.
((1 2) 3 4)
| \ \
3 4
|\
1 2
위와 같이 나타낼 수 있다.
연습문제 2.24
(list 1 (list 2 (list 3 4))) 계산할 때, 실행기가 어떤 값을 찍어내는지, 상자와 화살표/나무꼴 구조로 그려 보아라.
연습문제 2.25
다음 리스트에서 7을 끄집어내려면 어떻게 연산을 해야 하는가?
(define exam1 (list 1 3 (list 5 7) 9))
(define exam2 (list (list 7)))
(define exam3 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (cdr exam1)))))
(car (car exam2))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr exam3))))))))))))
연습문제 2.27
리스트의 부분 리스트까지 모두 뒤집는 deep-reverse 프로시저를 짜 보아라.
(define (deep-reverse li)
(define (deep-reverse-iter li result)
(cond ((null? li) result)
((not (pair? (car li)))
(deep-reverse-iter (cdr li) (cons (car li) result)))
(else
(deep-reverse-iter (cdr li) (cons (deep-reverse (car li)) result)))))
(deep-reverse-iter li ()))
(deep-reverse (list (list 1 2) (list 3 4)))
; ((4 3) (2 1))
연습문제 2.28
tree를 인자로 받아서, 모든 리프 노드 값을 일렬로 가지고 있는 리스트를 리턴하는 프로시저 fringe를 작성하라.
(define (fringe li)
(cond ((null? li) ())
((not (pair? li)) (list li))
(else (append (fringe (car li)) (fringe (cdr li))))))
(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)
연습문제 2.29
모빌이라는 자료구조로 여러 하위 문제들을 풀어보자.
(define (make-mobile left right)
(list left right))
(define (make-branch length structure)
(list length structure))
a. 모빌에서 가지를 골라내는 left-branch, right-branch 프로시저와 가지의 구성 요소를 골라내는 branch-length, branch-structure 프로시저를 정의하라.
(define (left-branch mb)
(car mb))
(define (right-branch mb)
(car (cdr mb)))
(define (branch-length br)
(car br))
(define (branch-structure br)
(car (cdr br)))
주의해야 할 것은 모빌과 branch가 list 구조이기 때문에, (left (right ())) 이렇게 구성 되어 있으므로 right에 접근하려면 cdr 후 car을 한번 더 해주어야 한다.
b. 모빌의 전체 무게를 구하는 total-weight 프로시저를 정의하라.
(define (total-weight mb)
(if (not (pair? mb))
mb
(let ((lfs (branch-structure (left-branch mb)))
(rfs (branch-structure (right-branch mb))))
(+ (total-weight lfs)
(total-weight rfs)))))
(define mb1 (make-mobile (make-branch 12 5) (make-branch 4 (make-mobile (make-branch 2 5) (make-branch 1 10)))))
(total-weight mb1)
; 20
c. 모빌이 balanced 하다는 말은, 모든 부분 모빌들이 balanced 하고, 해당 모빌의 좌 우 가지의 돌림합(해당 가지의 길이 * 가지에 매달린 추 무게 합)이 같다는 말이다. 모빌이 balanced 한지 밝히는 프로시저를 정의하라.
(define (balanced? mb)
(if (not (pair? mb))
#t
(let ((lfs (branch-structure (left-branch mb)))
(rfs (branch-structure (right-branch mb)))
(lfl (branch-length (left-branch mb)))
(rfl (branch-length (right-branch mb))))
(and (balanced? lfs)
(balanced? rfs)
(= (* lfl (total-weight lfs))
(* rfl (total-weight rfs)))))))
(balanced? mb1)
; #t
d. constructor를 아래와 같이 재정의 했을 때, 어떤 프로시저를 수정해야 하는지 밝히시오.
(define (make-mobile left right)
(cons left right))
(define (make-branch length structure)
(cons length structure))
; 원래 list로 구현했던 부분들을 pair로 구현하도록 수정.
; (left (right ())) => (left right) 로 바뀌게 되므로
(define (right-branch mb)
(cdr mb))
(define (branch-structure br)
(cdr br))
; 위와 같이 오른쪽 요소에 접근하는 로직을 단순화 할 수 있다.