lisp 함수 구체화

Question

나는 Graham Common Lisp Chapter 5 실습 5를했는데, 이것은 객체 X와 벡터 V를 취하는 함수를 필요로하며, V에서 X 바로 앞의 모든 객체의 목록을 반환한다.

(defun preceders (obj vec &optional (result nil) &key (startt 0)) 
    (let ((l (length vec))) 
    (cond ((null (position obj vec :start startt :end l)) result) 
      ((= (position obj vec :start startt :end l) 0) 
      (preceders obj vec result 
         :startt (1+ (position obj vec :start startt :end l)))) 
      ((> (position obj vec :start startt :end l) 0) 
      (cons (elt vec (1- (position obj vec :start startt :end l))) 
       (preceders obj vec result 
          :startt (1+ (position obj vec 
               :start startt 
               :end l)))))))) 

제대로 작동하지만 선생님은 나에게 다음과 같은 비판을 제공합니다 : 나는 재귀 버전을 수행 한

> (preceders #\a "abracadabra") 
(#\C#\d #r) 

: 같은

그것은 작동

"길이가 반복적으로 호출됩니다. 벡터로 그렇게 나쁘지는 않지만 여전히 불필요합니다. 보다 효율적이고 융통성있는 (사용자를위한) 코드는 다른 시퀀스 처리 기능과 마찬가지로이를 정의하는 것입니다. 다음을 사용하십시오 : start 및 : end 키워드 매개 변수, 다른 시퀀스 함수가하는 방식, 동일한 기본 초기 값. 길이는 많아야 한 번만 호출해야합니다. "

나는 Common Lisp 교과서와 Google과 상담하고 있지만이 비트에는 약간의 도움이있는 것처럼 보입니다."사용 방법 : 시작 : 시작 and : end keyword parameters "라고 말하면서"길이를 한 번만 호출하는 "방법에 대한 단서가 없습니다. 선생님이 게시 한 요구 사항을 충족시키기 위해 코드를 수정하는 방법에 대해 의견을 개진 할 수 있다면 고맙겠습니다. 감사합니다. 많은

는 UPDATE :!

(defun preceders (obj vec 
        &optional (result nil) 
        &key (start 0) (end (length vec)) (test #'eql)) 
    (let ((pos (position obj vec :start start :end end :test test))) 
    (cond ((null pos) result) 
      ((zerop pos) (preceders obj vec result 
           :start (1+ pos) :end end :test test)) 
      (t (preceders obj vec (cons (elt vec (1- pos)) result) 
         :start (1+ pos) :end end :test test))))) 

:

안녕 얘들 아, 이제 나는 다음과 같은 코드로 올라와있다

나는이 비판을받을 :

"하나 개 이상의 지점에서 동일하게 반복되는 복잡한 재귀 호출을 할 때, 사용 후, 호출 첫을 지역 변수에 저장하고, 자주 간단합니다 훨씬 간단 IF 또는 COND에서 변수 "

또한이 함수 내 반복 버전 :.

(defun preceders (obj vec) 
    (do ((i 0 (1+ i)) 
     (r nil (if (and (eql (aref vec i) obj) 
         (> i 0)) 
        (cons (aref vec (1- i)) r) 
        r))) 
     ((eql i (length vec)) (reverse r)))) 

나는 비판을받을

"더 나은 시점에서 DO 시작 및 반복 된 0 테스트 제거"

아이디어를 나에게 알려주세요. 성공을 향한 나의 마지막 단계라고 생각합니다. 많은 감사!

Answer 1

이러한 기능의 일반적인 매개 변수 목록은 다음과 같습니다

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
         (test #'eql)) 
    ... 
) 

당신이 시작과 끝 매개 변수가 볼 수 있듯이.

TEST가 기본 비교 함수입니다. Use (funcall 테스트 항목 (aref vector i)). KEY 매개 변수가 종종 있습니다 ...

LENGTH는 PRECEDERS의 모든 재귀 호출마다 반복적으로 호출됩니다.

비 재귀 버전을 수행하고 첫 번째 항목과 다음 항목에 대한 두 개의 인덱스를 벡터 위로 이동합니다.다음 항목이 찾고있는 항목에 대한 EQL 일 때마다 첫 번째 항목을 결과 목록으로 밀어 넣으십시오 (해당 항목이없는 경우).

재귀 버전의 경우 PRECEDERS가 호출하는 두 번째 함수를 작성합니다.이 함수는 0과 1로 시작하는 두 개의 인덱스 변수를 사용하고이를 사용합니다. 나는 POSITION에 전화하지 않을 것이다. 보통이 함수는 PRECEDERS 내부의 LABELS를 통한 로컬 함수이지만 좀 더 작성하기 쉽도록 도우미 함수가 외부에있을 수 있습니다.

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
         (test #'eql)) 
    (preceders-aux item vector start end test start (1+ start) nil)) 


(defun preceders-aux (item vector start end test pos0 pos1 result) 
    (if (>= pos1 end) 
     result 
     ... 
)) 

그게 도움이 되나요? 이미 작동하고 해결책을 가지고 있기 때문에

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
         (test #'eql)) 
    (let ((result nil)) 
    (loop for i from (1+ start) below end 
      when (funcall test item (aref vector i)) 
      do (pushnew (aref vector (1- i)) result)) 
    (nreverse result))) 

Answer 2

것은, 내가 주로 Rainer Joswig's solution을 amplifiy 것이다 관련 문체 의견을 위해 :

여기에 루프를 사용하여 반복 버전입니다.

(defun preceders (obj seq &key (start 0) (end (length seq)) (test #'eql))   
    (%preceders obj seq nil start end test)) 

주된 이유

는 결과에 대한 선택적 인수를 제거하는 것입니다 (I 함수는 "개인"임을 나타내는 %PRECEDERS, 공통의 규칙을 호출) 별도의 도우미 기능이 있습니다. 선택적 인수를 일반적으로 잘 사용하지만 선택 사항과 키워드 인수는 끔찍하게 함께 작동하며 단일 함수에 둘 다 있으면 매우 어려운 디버깅 오류를 생성하는 매우 효율적인 방법입니다.

도우미 기능을 전역 (DEFUN 사용) 또는 로컬 (LABELS 사용)으로 만들지 여부는 미비합니다. 들여 쓰기가 적고 대화 형 디버깅이 쉬워 졌기 때문에 전역으로 만드는 것이 더 좋습니다. YMMV.

도우미 기능의 가능한 구현은 다음과 같습니다

이

(defun %preceders (obj seq result start end test) 
    (let ((pos (position obj seq :start start :end end :test test))) 
     ;; Use a local binding for POS, to make it clear that you want the 
     ;; same thing every time, and to cache the result of a potentially 
     ;; expensive operation. 
    (cond ((null pos) (delete-duplicates (nreverse result) :test test))    
      ((zerop pos) (%preceders obj seq result (1+ pos) end test)) 
      ;; I like ZEROP better than (= 0 ...). YMMV. 
      (t (%preceders obj seq 
         (cons (elt seq (1- pos)) result) 
         ;; The other little bit of work to make things 
         ;; tail-recursive.  
     (1+ pos) end test))))) 

는 또한 모든 그 후, 나는 내가 대신 재귀의 명시 적 루프와 함께이 일을 레이너의 조언에 동의 것을 지적해야한다고 생각, 재귀 적으로 반복하는 것은 운동의 일부가 아닙니다.

편집 : 헬퍼 기능에 대한 더 일반적인 "%"규칙으로 전환했습니다. 일반적으로 사용하는 규칙은 공용 인터페이스를 구성하는 함수를 명시 적으로 만 내보낼 수 있지만 일부 표준 함수와 매크로는 변형 기능을 나타 내기 위해 후행하는 "*"를 사용합니다.

표준 DELETE-DUPLICATES 기능을 사용하여 중복 된 선행사를 삭제하는 방법이 변경되었습니다. 이는 적어도 EQ, EQL 및 EQUAL과 같은 일반적인 테스트 기능에 대해 내부적으로 해시 된 세트 표현을 사용할 수 있기 때문에 ADJOIN 또는 PUSHNEW의 반복 사용보다 훨씬 빠르게 (즉, 기하 급수적으로) 빠를 가능성이 있습니다.

Answer 3

첫 번째 업데이트에 대한 답변입니다.

첫 번째 질문 :

(bar (if (foo) 
     (+ 1 baz) 
     baz)) 

나 : 두 번째

(let ((newbaz (if (foo) 
       (+ 1 baz) 
       baz))) 
    (bar newbaz)) 

:

이 같은의이

(if (foo) 
    (bar (+ 1 baz)) 
    (bar baz)) 

를 참조

왜 I = 1로 시작하지 않습니까?

는 라이너에 의해 제안 된

Answer 4

반복적 인 버전이 아주 좋은 한 번만 순서를 통과하기 때문에 컴팩트하고 효율적인의 ... 내 다른 대답도 반복 버전을 참조하십시오; 과 달리 모든 반복에서 position을 호출하여 매번 하위 시퀀스를 통과합니다. 은 (편집 : 미안, 나는이 마지막 문장을 참조 라이너의 의견에 대해 완전히 잘못 해요), 또 다른 방법은 수집, 그것은 end을 충족 할 때까지 start을 사전에 재귀 버전이 필요한 경우

입니다 그 길을 따라 결과.

(defun precede (obj vec &key (start 0) (end (length vec)) (test #'eql)) 
    (if (or (null vec) (< end 2)) nil 
    (%precede-recur obj vec start end test '()))) 

(defun %precede-recur (obj vec start end test result) 
    (let ((next (1+ start))) 
    (if (= next end) (nreverse result) 
     (let ((newresult (if (funcall test obj (aref vec next)) 
         (adjoin (aref vec start) result) 
         result))) 
     (%precede-recur obj vec next end test newresult))))) 

은 물론 이것은 loop 버전을 표현하는 또 다른 방법입니다.

시험 : 또한

[49]> (precede #\a "abracadabra") 
(#\r #\C#\d) 
[50]> (precede #\a "this is a long sentence that contains more characters") 
(#\Space #\h #\t #\r) 
[51]> (precede #\s "this is a long sentence that contains more characters") 
(#\i #\Space #\n #\r) 

, I 해요 그는 재귀 알고리즘에 adjoin 또는 pushnew를 사용하여 좋아하지 않는 이유 로버트는, 선생님이 말씀 하셨 는가에 관심?

Answer 5

라이너의 루프 버전의 약간 modofied 변형 : 이것은 루프 지침을 더 사용하게하고, 다른 것들 사이에 한 번만 벡터의 각 요소에 액세스

(defun preceders (item vector 
        &key (start 0) (end (length vector)) 
        (test #'eql)) 
    (delete-duplicates 
    (loop 
     for index from (1+ start) below end 
     for element = (aref vector index) 
     and previous-element = (aref vector (1- index)) then element 
     when (funcall test item element) 
     collect previous-element))) 

(우리는 이전에 이전 요소를 유지 요소 변수).