stable-union lisp

Question

두 개의리스트를 인수로 취하고 반복없는 두 개의 합집합 인리스트를 리턴하는 unisp 함수를 작성해야합니다. 입력의 것과 일치해야 주문

예를 들어

을 나열 입력이 '(ABC)와'(ECD) 결과가 있어야한다 '를하는 경우 (abced)

다음

내가 지금까지

이 무엇

(defun stable-union (x y) 
    (cond 
    ((null x) y) 
    ((null y) x)) 
    (do ((i y (cdr i)) 
     (lst3 x (append lst3 
         (cond 
         ((listp i) 
         ((null (member (car i) lst3)) (cons (car i) nil) nil)) 
         (t (null (member i lst3)) (cons i nil) nil))))) 
     ((null (cdr i)) lst3))) 

내 오류가 세그먼트와 "잘못된 함수 객체"(널 (회원 (자동차 전) lst3))

조언이 있다는 것입니다?

Answer 1

당신은 당신의 괄호에게있어 모든 뒤죽박죽 업 : 당신은 아마 수를 의도 한대로

(defun stable-union (x y) 
    (cond 
    ((null x) y) 
    ((null y) x) )  END OF COND form - has no effect 

    (do ((i y (cdr i)) 
     ^^ 
     (lst3 x (append lst3 
         (cond 
         ((listp i) 
         ( (null (member (car i) lst3)) 
         ^^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ called as a function 
          (cons (car i) nil)   with two arguments 
          nil )) 
           ^^ 
         (t       NEXT 3 forms have no effect 
          (null (member i lst3)) 
          (cons i nil) 
          nil   ))))) 
              ^^ 
     ((null (cdr i)) lst3))) 

여기 수정 parenthesization로, 코드 그리고 필요한 경우 일부 if의 추가 :

(defun stable-union (x y) 
    (cond 
    ((null x) y) 
    ((null y) x) 
    (t 
    (do ((i y (cdr i)) 
     (lst3 x (append lst3 
        (cond 
        ((listp i) 
         (if (null (member (car i) lst3)) 
          (cons (car i) nil) 
          nil)) 
        (t 
         (if (null (member i lst3)) 
          (cons i nil) 
          nil)))))) 
     ((null (cdr i)) lst3))))) 

이 코드에는 여전히 문제가 있습니다. do 논리가 잘못되었으므로 하나의 요소 만 포함되어 있으면 y의 첫 번째 요소는 건너 뜁니다. 그리고 그것이 필요하든 없든 항상 append으로 전화하십시오. (append lst3 nil)을 호출하면 lst3에 최상위 cons 셀의 복사본이 완전히 추가됩니다.

이러한 긴 문장은 일반적으로 do의 로컬 변수에 대한 업데이트 양식이 아닌 do 본문에 있습니다.

---

하지만 당신은 어디 do, 적절한의보다 전문적인 양식을 사용할 수 있습니다. 여기에 자연스럽게 dolist을 사용합니다. "wvxvw"'s lead on using hash-tables for membership testing에 따라, 우리는 쓰기 :

(defun stable-union (a b &aux (z (list nil))) 
    (let ((h (make-hash-table)) 
     (p z)) 
    (dolist (i a) 
     (unless (gethash i h) 
     (setf (cdr p) (list i) p (cdr p)) 
     (setf (gethash i h) t))) 
    (dolist (i b (cdr z)) 
     (unless (gethash i h) 
     (setf (cdr p) (list i) p (cdr p)) 
     (setf (gethash i h) t))))) 

내가 "머리 센티넬"라고 부르는 기술을 사용하여 (z 변수 사전 초기화 싱글 목록) 맨 다운 목록 건물에 대한 코드의 큰 단순화 수 있습니다 하나의 여분의 cons 셀 할당 비용.

Answer 2

(remove-duplicates (append '(a b c) '(e c d)) :from-end t) 

Answer 3

(null (member (car i) lst3))을 평가 한 결과를 실행하려고했기 때문에 오류가 발생했습니다. 내가가리스트 경우 콘드 표현에서, 그것은 표현

((null (member (car i) lst3)) (cons (car i) nil) nil)) 

을 평가하고 결과를 반환하려고 시도합니다. 표현식의 첫 번째 요소는 함수 여야하지만

(null (member (car i) lst3)) 

부울 값을 반환합니다. 따라서 실패. 코드 구조에는주의가 필요합니다. 당신이 놓친 것은 내부에 cond이 필요하다는 것입니다.

덧붙여 말하자면, 재귀 적으로 수행하면 훨씬 더 깨끗한 함수가됩니다.

나는 Lisper가 아닌 Schemer이지만 약간 생각했다. 여기에 재귀 구현의 뼈대는 다음과 같습니다

(defun stable-union (x y) 
    (cond 
    ((null x) y) 
    ((null y) x) 
    ((listp y) 
    (cond 
     ((member (car y) x) (stable-union ??? (???))) 
     (t (stable-union (append x (??? (???))) (cdr y))))) 
    ((not (member y x)) (append x (list y))) 
    (t x))) 

당신이 do 진형 때문에

Answer 4

(그것을 안보에 대한 의지 네스에, 두 번째 마지막 줄에 감사 간단한 tyop를 해결하기 수정 됨), 및 재귀 때문에 솔루션은 여기에 당신이 한 수 무엇을, 더 악화 될 것이다 : 이것은 아직 차 시간, 그리고 행동 등이다

(defun union-stable (list-a list-b) 
    (do ((i list-b (cdr i)) 
     filtered back-ref) 
     ((null i) (append list-a back-ref)) 
    (unless (member (car i) list-a) 
     (if back-ref 
      (setf (cdr filtered) (list (car i)) 
       filtered (cdr filtered)) 
      (setf back-ref (list (car i)) 
       filtered back-ref))))) 

그 첫 번째 목록은 중복을 가지고, 또는 두 번째 목록은없는 중복을 가지고있는 경우 첫 번째 목록에서 - 있을거야. 이 함수를 "공용체"라고 부르는 것이 얼마나 공정한 지 잘 모르겠지만, 통합을 시도하기 전에 중복이있는 경우 목록과 관련하여 정의해야합니다.

운동을하기보다는 결과에 관심이 있다면 그렇게했을 것입니다. 요소가 입력 목록에서 반복 되더라도 요소가 고유하다는 것을 보장합니다.

(defun union-stable-hash (list-a list-b) 
    (loop for c = (car (if list-a list-a list-b)) 
    with back-ref 
    with hash = (make-hash-table) 
    for key = (gethash c hash) 
    with result 
    do (unless key 
      (if back-ref 
       (setf (cdr result) (list c) 
        result (cdr result)) 
       (when (or list-a list-b) 
       (setf back-ref (list c) 
         result back-ref))) 
      (setf (gethash c hash) t)) 
    do (if list-a (setf list-a (cdr list-a)) 
      (setf list-b (cdr list-b))) 
    do (unless (or list-a list-b) 
      (return back-ref))))