2019년 1월 17일 목요일

[on lisp] 5.6 Recursion on Subtrees

5.6 Recursion on Subtrees
리스프 프로그램에서 흔히 볼 수 있는 또 다른 재귀 패턴이 있다. 서브트리의 재귀
이 패턴은 중첩 리스트로 시작하여 car와 cdr을 모두 재귀적으로 사용하려는 경우에 나타남.

lisp 리스트는 다재다능한 구조이다. 리스트는 시퀀스, 세트, 매핑, 배열 및 트리를 나타낼 수 있다.
리스트를 트리로 해석하는 몇 가지 방법이 있다. 가장 보편적인 것은 왼쪽 가지가 car이고 오른쪽 가지가 cdr인 이진 트리로 간주하는 것이다.
;; Figure 5.7: Lists as trees.
(a . b) 
(a b c) 
(a b (c d))
만약 리스트가 아래와 같은 형태로 고려되면 쉽게 해석할 수 있다.
(a b c) = (a . (b . (c . nil))) 
(a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))
어떠한 형태의 리스트도 2진트리로 해석될 수 있다. copy-list와 copy-tree와 같은 공통 리스프 함수의 쌍 간의 구별을 돕는다.
전자는 리스트를 시퀀스로 간주하고 복사한다. 만약 리스트에 서브리스트(sublists)를 보유한다면, 그것이 해당 리스트의 요소일 뿐이라도 복사되지 않는다.
(setq x '(a b) listx (list x 1))
((A B) 1)
(eq x (car (copy-list listx)))
T
;; copy-list구현을 다시 보자.
;; copy-list
(lrec #'(lambda (x f) (cons x (funcall f))))
;; Figure 5.5: Function to define flat list recursers
;; 이전에 본 소스임.
;; 특이하게 함수를 리턴함
(defun lrec (rec &optional base) 
  (labels ((self (lst) 
    (if (null lst) 
     (if (functionp base) 
      (funcall base) 
   base) 
  (funcall rec (car lst) 
               #'(lambda () (self (cdr lst))))))) 
 #'self))

;; 반대로 copy-tree는 리스트를 트리로 간주한다.
;; 서브리스트들 전부 복사된다.
(eq x (car (copy-tree listx)))
NIL
copy-tree구현체를 봐보자.
(defun our-copy-tree (tree)
  (if (atom tree)
      tree
      (cons (our-copy-tree (car tree))
            (if (cdr tree) (our-copy-tree (cdr tree))))))

댓글 없음 :

댓글 쓰기