이 절에는 리스트를 탐색하는 함수의 몇 가지 예가 수록되어있다.
커먼리습은 이것을 위해 풍부한 빌트인 연산자를 제공하지만, 일분 작업들은 여전히 어렵거나, 적어도 효율적으로 수행하기 어렵다.
일단 우리는 그 전에 리스트 안에 리스트들을 모두 순회하는 함수들을 알아보자. 이전에는 최상위 리스트 (1차원)만을 매개변수로 받았지만
이번에는 다르다. 아래처럼 실행이 될 것이다.
flatten은 평평하게 만드는 것이고, prune(가지치다) evenp인 녀석은 없애버린다.
> (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))유틸리티 코드의 소스를 보자.
Figure 4.3: Doubly-recursive list utilities.
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc) ;; x가 끝나면 acc리턴
((atom x) (cons x acc)) ;; x가 cons가 아닌 요소 하나라면 acc와 cons로 합침. 그리고 리턴
(t (rec (car x) (rec (cdr x) acc)))))) ;; 나머지: 나머지요소와 acc를 마저 재귀돌리고 다 돌리면 첫번째 요소와 합친다.
(rec x nil))) ;; acc 는 nil로 시작한다.
;; 보면 알겠지만 안으로 계속 들어가면서 car으로 빼내서 acc에 계속 더한다.
(defun prune (test tree)
(labels ((rec (tree acc)
(cond ((null tree) (nreverse acc)) ;; 1. tree가 더이상 없다면 리턴
((consp (car tree)) ;; 2. tree가 cons다 더 있다.
(rec (cdr tree) ;; 2.2 나머지 트리를 남겨서 재귀를 돌림.
(cons (rec (car tree) nil) acc))) ;; 2.1 하나짜리는 따로 (rec (car tree) nil) 로 보내서 (funcall test...) 에 들어가도록 하여 테스트를 진행한다.
(t (rec (cdr tree)
(if (funcall test (car tree))
acc ;; 테스트에 맞으면 누산기 리턴
(cons (car tree) acc))))))) ;; 틀리면 누산기에 더해서 리턴
(rec tree nil)))
이제 다음 유틸리티 소스들을 구경해보자.
before함수는 리스트에서 한 개체가 다른 개체보다 먼저 발견되는지 여부를 알려준다.
> (before 'b 'd '(a b c d)) (B C D) ;; b가 d앞에 있는지 ;; 아래처럼 적당히 얼버무려서 raw Lisp로 풀 수도 있다. > (< (position 'b '(a b c d)) (position 'd '(a b c d)))하지만 뒤에 코드는 비효율적이며 에러가 나기 쉽다. 비효율적인 이유: 우리는 두 객체를 모두 찾을 필요가 없다. 둘 다 순회하다가 한놈만 찾으면 게임은 끝난다. 에러나기 쉬운 이유: 만약 객체가 리스트가 아닌 경우, nil이 '<'계산을 위한 매개변수로 들어올 것이다. before의 특이한 점은 옵셔널 값이 있다는 점이다. 그래서 값이 없으면 기본값으로 비교를 하고 커스텀을 하려면 다른 함수를 넣으면 된다. 이 녀석은 test라는 이름에 매핑된다.
;; fig 4.4
(defun find2 (fn lst)
(if (null lst)
nil
(let ((val (funcall fn (car lst))))
(if val
(values (car lst) val)
(find2 fn (cdr lst))))))
(defun before (x y lst &key (test #'eql))
(and lst
(let ((first (car lst)))
(cond ((funcall test y first) nil)
((funcall test x first) lst)
(t (before x y (cdr lst) :test test))))))
(defun after (x y lst &key (test #'eql))
(let ((rest (before y x lst :test test)))
(and rest (member x rest :test test))))
;; :test -- a designator for a function of two arguments that returns a generalized boolean.
(defun duplicate (obj lst &key (test #'eql))
(member obj (cdr (member obj lst :test test))
:test test))
(defun split-if (fn lst)
(let ((acc nil))
(do ((src lst (cdr src)))
((or (null src) (funcall fn (car src)))
(values (nreverse acc) src))
(push (car src) acc))))
before에 첫번째 인수가 두번째 인수보다 먼저 나오면 참이다. (원래 그러려고 만든거다)즉, 두번째 인수가 리스트에서 전혀 보이지 않아도 참이다.
> (before 'a 'b '(a)) (A)after를 호출하면 정확히 알 수 있다. 이 테스트에서는 두 인수가 모두 리스트안에 있어야 한다.
일단 이걸 이해하려면 member에 대해 알아야 한다. 아래처럼 동작한다.
(member 2 '(1 2 3)) ; (2 3) (member 2 '((1 . 2) (3 . 4)) :test-not #'= :key #'cdr) ; ((3 . 4)) > (after 'a 'b '(b a d)) (A D) > (after 'a 'b '(a)) NILduplicate함수는 중복되는 것이 생기면 그곳에서 멈추고 cons를 뱉는다. 그러면 뒤에 연결된 아이들도 보일 것이다.
좀 더 까다로운 언어 디자이너들은 Common Lisp가 거짓과 빈 리스트를 모두 나타내기 위해 nil을 사용한다는 것에 충격을 받는다.
때로는 문제를 일으키기도 하지만(14.2 참조, 나중에 보자), 중복과 같은 기능에서 편리하다.
마지막의 member함수는 어떤 조건에 따라 리스트를 나눈다.
> (split-if #'(lambda (x) (> x 4)) '(1 2 3 4 5 6 7 8 9 10)) (1 2 3 4) (5 6 7 8 9 10)리턴이 2개가 되고 하나를 출력하려 하면 첫번째 것만 보인다.
Figure4.4를 넘어가서 Figure4.5 를 보자.
;; Figure 4.5: Search functions which compare elements.
(defun most (fn lst)
(if (null lst)
(values nil nil)
(let* ((wins (car lst))
(max (funcall fn wins)))
(dolist (obj (cdr lst))
(let ((score (funcall fn obj)))
(when (> score max)
(setq wins obj
max score))))
(values wins max))))
(defun best (fn lst)
(if (null lst)
nil
(let ((wins (car lst)))
(dolist (obj (cdr lst))
(if (funcall fn obj wins)
(setq wins obj)))
wins)))
(defun mostn (fn lst)
(if (null lst)
(values nil nil)
(let ((result (list (car lst)))
(max (funcall fn (car lst))))
(dolist (obj (cdr lst))
(let ((score (funcall fn obj)))
(cond ((> score max)
(setq max score
result (list obj)))
((= score max)
(push obj result)))))
(values (nreverse result) max))))
Figure4.5 에는 다른 종류의 검색 기능을 포함한다.첫번째, most함수, 한 번에 하나의 요소만 확인한다. 리스트와 점수를 매길함수를 주면, 가장큰 스코어를 낸 요소를 리턴한다.
아래 테스트에서는 중복된 값이 있으면 먼저된 녀석이 리턴된다.
> (most #'length '((a b) (a b c) (a) (e f g)))
(A B C)
3
;; 코드를 구경하자.
(defun most (fn lst)
(if (null lst) ;; lst가 없으면, nil nil을 뱉는다.
(values nil nil)
(let* ((wins (car lst)) ;; lst의 첫번째를 뽑는다.
(max (funcall fn wins))) ;; 첫번째의 값을 점수매겨서 max에 넣어본다.
(dolist (obj (cdr lst)) ;; lst의 나머지를 반복문 돌린다.
(let ((score (funcall fn obj))) ;; 나머지 값 하나하나를 점수 매긴다.(score)
(when (> score max) ;; 만약 max보다 score가 크면
(setq wins obj ;; wins에는 큰 녀석의 요소와
max score)))) ;; max에는 score값는 넣는다.
(values wins max)))) ;; 끝나면 리턴한다.
좀 더 일반적인 검색은 best에서 보여주고 있다.
이 유틸리티는 함수와 리스트를 받는다. 그런데 여기서 함수는 꼭 두개의 인수를 받는 predicate이어야 한다.
이 predicate으로 나머지를 이긴 녀석을 리턴한다.
> (best #'> '(1 2 3 4 5))
5
;;역시 코드를 파보자.
(defun best (fn lst)
(if (null lst) ;; 없으면 nil
nil
(let ((wins (car lst))) ;; lst의 첫번째 값을 일단 받아서 시작할 거다.
(dolist (obj (cdr lst)) ;; lst의 나머지를 obj라는 요소에 하나하나 담아서 반복문 실행
(if (funcall fn obj wins) ;; fn(predicate)에 obj,wins를 넣어서
(setq wins obj))) ;; 트루면 값을 바꾼다.
wins))) ;; 이긴놈을 리턴한다.
마지막으로 mostn을 보자.
함수와 리스트를 받아서 가장큰 스코어를 가진 요소들을 리스트로 리턴한다.
> (mostn #'length '((a b) (a b c) (a) (e f g)))
((A B C) (E F G))
;; 코드구경
(defun mostn (fn lst)
(if (null lst) ;; 없으면 nil
(values nil nil)
(let ((result (list (car lst))) ;; 첫번째 값을 리스트로 감쌈
(max (funcall fn (car lst)))) ;; 첫번째 값의 점수를 매기고 그걸 임시로 max에 넣음
(dolist (obj (cdr lst)) ;; 나머지부터 dolist로 실행
(let ((score (funcall fn obj))) ;; 요소를 점수매겨 score에 넣음
(cond ((> score max) ;; score가 max보다 크면
(setq max score ;; max를 score로 대체
result (list obj))) ;; result를 (list obj)로 대체
((= score max) ;; score == max 면
(push obj result))))) ;; result에 값을 추가.
(values (nreverse result) max))))
댓글 없음:
댓글 쓰기