There is another recursive pattern commonly found in Lisp programs: recursion on subtrees
리스프 프로그램에서 흔히 볼 수 있는 또 다른 재귀 패턴이 있다. 서브트리 재귀
This pattern is seen in cases where you begin with a possibly nested list, and want to recurse down both its car and its cdr.
이 패턴은 중첩 리스트로 시작, car,cdr를 이용하여 재귀적으로 트리 아래로 들어간다.
The Lisp list is versatile structure.
lisp 리스트는 다재다능한 구조이다.
Lists can represent, among other things, sequences, sets, mappings, arrays, and trees.
리스트는 시퀀스, 세트, 매핑, 배열 및 트리를 나타낼 수 있다.
There are serveral different ways to interpret a list as a tree.
리스트를 트리로 해석하는 몇 가지 방법이 있다.
The most common is to regard the list as a binary tree whose left branch is the car and whose right branch is the cdr
가장 보편적인 것은 왼쪽 가지가 car이고 오른쪽 가지가 cdr인 이진 트리로 간주하는 것이다.
Figure 5.7 shows three examples of lists and the trees they represent.
그림 5.7이 리스트(트리)의 3가지 예다.
;; Figure 5.7: Lists as trees. (a . b) (a b c) (a b (c d))이게 어떻게 트리냐고 보는데 점으로 연결된 b는 리스트(또는 그냥 값)으로 볼 수 있다.
그러므로 cdr 값은 subtree라고 보는 것이다.
아래 내용을 보면 이해가 쉬울 것이다.
(a b c) = (a . (b . (c . nil))) (a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))어떠한 형태의 리스트도 2진트리로 해석될 수 있다. 하여 copy-list와 copy-tree와 같은 공통 리스프 함수의 쌍 간의 구별이 필요하다.
The former copies a list as a sequence -if the list contains sublists, the sublists, being mere elements in the sequence, are not copied.
이 리스트를 시퀀스라 간주하고 복사해보자. 만약 리스트에 서브리스트(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구현체를 봐보자.;; 1. 매개변수가 리스트가 아니라면 리턴
;; 2. car 내용을 재귀로 들어감 (왼쪽 가지도 있을 수 있으니까)
;; 3. (cdr tree)해서 오른쪽 가지가 있따면, 그것도 재귀
;; 4. 왼쪽 오른쪽 cons로 합친다.
;; 5. 머지된거 리턴
(defun our-copy-tree (tree)
(if (atom tree)
tree ;; 1
(cons (our-copy-tree (car tree)) ;; 2
(if (cdr tree) (our-copy-tree (cdr tree)))))) ;; 3
트리에서 리프(leaves)의 갯수를 카운트 하는 예제를 만들어보자.
; 1. atom이면 1
; 2. (car tree) 왼쪽서브트리를 재귀
; 2.1 (cdr tree) 오른쪽서브트리가 있으면 재귀
; 2.3 (cdr tree) 오른쪽서브트리가 없으면(nil) 1 리턴
; 2.4 (+ 2.1 2.3) 재귀돈거 더하기
(defun count-leaves (tree)
(if (atom tree)
1
(+ (count-leaves (car tree))
(or (if (cdr tree) (count-leaves (cdr tree)))
1))))
A tree has more leaves than the atoms you can see when it is represented as a list:특이한 것이 있는데 리스트에 들어있는 것 보다 더 많은 숫자가 리턴된다는 것이다.
(count-leaves '((a b (c d)) (e) f)) 10The leaves of a tree are all the atoms you can see when you look at the tree in its dotted-paire representation.
리프는 트리에서 보이는 모든 아톰값을 말하는데, 지금 저 트리는 점으로 이루어진 쌍 값에서 안보이게 한게있음 (미관상)
A dotted-pair notation, ((a b (c d)) (e) f) would have four nils that aren't visible in the list representation (one for each pair of parentheses) so count-leaves returns 10.
dotted-pair에를 잘 보면 마지막에 꼭 '. nil'이 포함되어 있다. 이 nil은 소괄호 마다 마지막에 하나씩 있다.
그러므로 소괄호 하나에 nil은 하나씩 무조건 있기 때문에 4개가 더해진 것
In the last chapter we defined several utilities which operate on trees. For example, flatten(page 47) takes a tree and returns a list of all the atoms in it.
이전 챕터에서 트리에서 이용할 수 있는 유틸리티를 몇개 만들었다.
----잠깐 이전에 공부했던 내용 돌아보기 START
;; Fig 4.3 : Doubly-recursive list utilities
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec car x) (rec (cdr x) acc))))))
(rec x nil)))
;; 양쪽 순회가 가능해야 한다.
;; 1 tree가 널이면 acc를 반대로 돌려서 리턴
;; 2 (car tree)가 리스트이면
;; 2.1 (cdr tree)를 남은 트리로 놓고
;; 2.2 (car tree)를 따로 테스트해서 acc에 추가한다.
;; 3 (car tree)가 리스트가 아닌경우
;; 3.1 테스트가 맞는지 확인한다.
;; 3.2 맞으면 버리고 acc만 리턴
;; 3.3 틀리면 (cons (car tree) acc)로 acc에 값을 넣는다.
(defun prune (test tree)
(labels ((rec (tree acc)
(cond ((null tree) (nreverse acc))
((consp (car tree))
(rec (cdr tree)
(cons (rec (car tree) nil) acc)))
(t (rec (cdr tree)
(if (funcall test (car tree))
acc
(cons (car tree) acc))))))
(rec tree nil)))
Fig 4.3 shows two examples of functions that descend into(서서히 빠져들다) nested lists그림4.3은 nested list 안으로 들어가는 함수들을 보여준다.
flatten, 쫙펴주는 함수
prune, 은 순회하면서 없앤다. (remove-if같은 건가)
(flatten '(a (b c) ((d e) f))) (A B C D E F) (prune #'evenp '(1 2 (3 (4 5) 6) 7 8 (9))) (1 (3 (5)) 7 (9))----잠깐 이전에 공부했던 내용 돌아보기 END
이 flatten이 아래처럼 다시 쓸 수 있다.(비효율적으로)
하지만 꽤나 간결하다.
(defun flatten (tree)
(if (atom tree)
(mklist tree)
(nconc (flatten (car tree))
(if (cdr tree) (flatten (cdr tree))))))
find-if의 재귀버전을 마지막으로 보자. 일반리스트, 트리 모든 경우에 먹힌다.
Finally, consider rfind-if, a recursive version of find-if which works on tree as well as flat lists:
;; our-find-if는 비교용
(defun our-find-if (fn lst)
(if (funcall fn (car lst)
(car lst)
(our-find-if fn (cdr lst)))
(defun rfind-if (fn tree)
(if (atom tree)
(and (funcall fn tree) tree)
(or (rfind-if fn (car tree))
(if (cdr tree) (rfind-if fn (cdr tree))))))
To generalize find-if for trees, we have to decide whether we want to search for just leaves, or for whole subtrees.find-if를 트리용으로 일반화하려면, 리프만 원하는지 모든 서브트리를 원하는지 결정해야 한다.
Our rfind-if takes the former approach, so the caller can assume that the function given as the first argument will only be called on atoms:
여기서 보인 rfind-if는 전자의 접근방식을 이용한다. 하여 호출자는 첫번째 매개변수는 무조건 atom임을 가정할 수 있을 것이다. 그러므로 predicate으로 찾는게 이건지 확인할 때, 당연히 매개변수가 atom이라는 전재로 들어가야할 것이다.
(rfind-if (fint #'numberp #'oddp) '(2 (3 4) 5))
우리는 지금까지 4가지의 비슷한 형태의 함수를 보았다.
copy-tree, count-leaves, flatten 그리고 rfind-if.
Indeed, they're all instances of an archetypal function for recursion on subtress.
사실, 이것들은 서브트리에 재귀반복을 위한 전형적인 함수들이다.
As with recursion on cdrs, we need not leave this archetype to float vaguely in the background.
cdrs들로만 만든 재귀(일반리스트)와 마찬가지로, 우리는 이 원형을 이 상태로 남겨둬서, 4개의 함수들의 형태를 어정쩡하게 남길 필요는 없다. (다시 유틸리티 함수 같은 것을 만들어야 하지 않을까)
To get at the archetype itself, let's look at these functions and see what's not pattern.
이 원형 자체에 접근하기 위해서, 우리가 만든 4개의 함수 안에 어던 것이 패턴인지 아닌지 확인해보자.
Essentially our-copy-tree is two facts:
our-copy-tree는 두 요소가 있다.
1. In the base case it returns its argument.
base case가 걸린 경우 그 당시 재귀로 들어온 함수를 리턴한다.
2. In the recursive case, it applies cons to the recursions down the left (car) and right (cdr) subtress.
재귀를 해야 하는 case에 걸린 경우, cons로 왼쪽(car)으로 재귀 돈거랑 오른쪽(cdr)으로 재귀 돈 서브트리를 합친다.
이 두개의 요소를 바탕으로 아래처럼 쓸 수 있다.(유틸리티함수는 아래 보자)
(ttrav #'cons #'identity)ttrav("tree traverser")는 Figure 5.8에서 보여준다.
;; Fig 5.8 : Function for recursion on trees.
; rec(첫번째 매개변수)는
(defun ttrav (rec &optional (base #'identity))
(labels ((self (tree)
(if (atom tree)
(if (functionp base)
(funcall base tree)
base)
(funcall rec (self (car tree))
(if (cdr tree)
(self (cdr tree)))))))
#'self))
Instead of passing one value in the recursive case, we pass two, one for the left subtree and one for the right. 재귀를 하는 case에서 값을 하나 보내는 대신, 2개를 보낸다. (왼쪽 서브트리, 오른쪽 서브트리)
If the base argument is a function it will be called on the current leaf.
만약 base매개변수가 함수라면 현재 상태가 리프에 있을 때 실행됨.
In flat list recursion, the base case is always nil, but in tree recursion the base case could be an interesting value, and we might want to use it.
일반 리스트 재귀서는 base case가 항상 nil이다, 하지만 트리재귀에서 base case는 그것과는 아주 다른 값이 될 수 있으며, 그걸 사용하고 싶을 것이다.
With ttrav we could express all the preceding functions except rfind-if.
ttrav는 rfind-if를 제외하고 다른 함수들을 모두 표현할 수 있다.
; our-copy-tree (ttrav #'cons) ; count-leaves ; (or r 1)은 순회하다가 요소가 nil이 아니면 그걸 뱉는다고 보자. ; r이 nil 이면 1로 리턴 ; 두번째 값은 optional인데 1로 넣었다. base case인 경우 1을 리턴 (ttrav #'(lambda (l r) (+ 1 (or r 1))) 1) ; flatten ; nconc로 재귀하고 합치는 거 (ttrav #'nconc #'mklist)To define rfind-if we need a more general tree recursion builder which gives us control over when, and if, the recursive calls are made.
rfind-if를 정의하려면 좀 더 일반화된 트리 재귀 빌더(함수)가 필요하다.
이 함수는 when,if 그리고 재귀함수를 만드는 그 상황도 우리가 조절할 수 있어야 하다.
(ttrav는 무조건 트리의 모든 곳을 순회한다.find-if는 찾으면 멈춰야 한다.)
As the first argument to ttrav we gave a function which took the results of the recursive calls.
ttrav에서 첫번째 매개변수는 재귀호출의 결과를 받는 함수였다.
For the general case, we want to use instead a function which takes two closures representing the calls themselves.
이제 일반적인 함수에서는 우리는 대신 다른 함수를 사용할 건데, 자기자신을 호출하는 두개의 클로저를 받는다.(??)
Then we can write recursers which only traverse as much of the tree as they want to.
그렇게면 우리는 우리가 원하는 만큼만 순회하는 recurser(재귀호출하는 녀석?)를 작성할 수 있다.
; Fig 5.10: Function for recursion on trees
; 1 lambda로 self를 바로 실행되지 않도록 하였다.
(defun trec (rec &optional (base #'identity))
(labels
((self (tree)
(if (atom tree)
(if (functionp base)
(funcall base tree)
base)
(funcall rec tree
#'(lambda () ; 1
(self (car tree)))
#'(lambda ()
(if (cdr tree)
(self (cdr tree))))))))
#'self))
Fig 5.10을 보자.The second arg to trec should be a function of three argument:
두번째 매개변수는 3개의 매개변수를 받는 함수여야 한다.
the current object and the two recursers.
현재 객체와 두개의 recurser(left/right 인듯)가 들어간다.
The latter two will be closures representing the recursions down the left and right subtress.
뒤에 두 매개변수는 왼쪽 오른쪽 서브트리를 재귀로 들어가는 녀석이다.
특이한 것이 이 두 함수는 각자 왼쪽/오른쪽 서브트리를 클로저로 가져간다.
With trec we would define flatten as:
trec 이용하여 flatten을 만들어자.
; (conc l r)에서 (nconc (l) (r))로
(trec #'(lambda (o l r) (nconc (funcall l) (funcall r)))
#'mklist)
;; ttrav 버전을 다시 보자
(ttrav #'conc #'mklist)
이제 rfind-if를 보자(oddp를 접목하자);; (or l r)에서 (or (l) (r))
;; or은 값이 있으면 바로 리턴하고 다음 것은 평가하지 않는다.
;; lambda로 묶어놓은 이유가 바로 이거다.(중요)
(trec #'(lambda (o l r) (or (funcall l) (funcall r)))
#'(lambda (tree) (and (oddp tree) tree)))
; 비교용
(defun rfind-if (fn tree)
(if (atom tree)
(and (funcall fn tree) tree)
(or (rfind-if fn (car tree))
(if (cdr tree) (rfind-if fn (cdr tree))))))
이렇게 #'(lambda)로 감싸서 바로 실행되지 않도록 하였다.잘 보면
