Lisp 함수 : 공용어

Question

나는 혀짤배기 숙제가있다. 힘들어한다.

공용 작업을 수행하는 함수를 작성해야합니다. 이 함수는 두 개의 입력을 원자 또는 목록의 형태로 사용하고 모든 요소를 ​​결합하여 순서를 유지하고 모든 수준의 괄호를 제거합니다.

함수의 출력은 :

(my-union 'a 'b)       ;; (a b) 
(my-union 'a '(b))      ;; (a b) 
(my-union '(a b) '(b c))     ;; (a b c) 
(my-union '(((a))) '(b(c((d e))a)))  ;; (a b c d e) 

나는 LISP 상당히 새로운입니다. 여기 는 내가 지금까지 쓴 무엇이며, 그것은 단지 세 번째 예를 들어 작동합니다

(defun new-union (a b) 
(if (not b) 
     a 
     (if (member (car b) a) 
     (new-union a (cdr b)) 
     (new-union (append a (list (car b))) (cdr b))))) 

어떤 도움을 주시면 감사하겠습니다!

Answer 1

, 여기에없는 성능에 대한 걱정, 그리고 CL이 제공하는 도구를 잘 사용하고, 아주 간단한 하향식 (top-down) 접근 방식 중복을 제거하는 함수가 이미 있습니다 : remove-duplicates. :from-end 키워드 인수와 함께 사용하면 "주문 보존"됩니다. 이제 임의의 중첩 목록을 평평하게하는 함수 flatten이 있다고 상상해보십시오. 그런 다음 질문에 대한 해결책은 다음과 같습니다

(defun new-union (list1 list2) 
    (remove-duplicates (flatten (list list1 list2)) :from-end t)) 

이 더 이상 제한이 주어지지 때이 문제를 접근 할 방법이며, 성능에 대해 많이 걱정하는 진짜 이유가 없다. 가능한 한 많은 도구 상자를 사용하고 필요하지 않으면 바퀴를 다시 열지 마십시오.

이렇게 문제가 발생하면 flatten 함수를 작성하는 데 익숙해 져 있습니다.이 연습은 제가 연습 문제로 남겨 둘 것입니다. 너무 어렵지 않습니다. 쉬운 옵션 중 하나는 재귀 함수를 작성하여 다음과 같은 문제에 접근하는 것입니다.

병합 할 목록의 첫 번째 요소 자체가 목록 인 경우 병합 된 첫 번째 요소를 병합 된 나머지 부분에 추가하십시오 . 첫 번째 요소가 목록이 아닌 경우 목록의 병합 된 나머지 부분 앞에 추가하십시오. 입력이 전혀 목록이 아니면 그냥 반환하십시오.

좋은 연습이되어야하며 몇 줄의 코드만으로 수행 할 수 있습니다.

(매우 올바른 경우 도우미 함수를 사용하여 작업을 수행하고 인수가 실제로 목록인지 여부를 확인하십시오. 그렇지 않으면 원자에 대해서도 flatten이 작동합니다. 당신을 위해 문제)

지금, 당신은 flatten을 쓴 가정 :.

> (defun new-union (list1 list2) 
    (remove-duplicates (flatten (list list1 list2)) :from-end t)) 
NEW-UNION 
> (new-union 'a 'b) 
(A B) 
> (new-union 'a '(b)) 
(A B) 
> (new-union '(a b) '(b c)) 
(A B C) 
> (new-union '(((a))) '(b (c ((d e)) a))) 
(A B C D E) 

Answer 2

이 방법에 접근하는 한 가지 방법은 우려를 분리하는 것입니다. 하나는 평평하다. 다른 것은 중복 제거입니다. 또 다른 결과는 결과입니다.

결과로 빈 목록으로 시작하여 이미 결과에있는 요소를 건너 뛰고 첫 번째 목록의 요소를 추가합니다.

그런 다음 두 번째 목록 요소를 동일한 결과 목록에 추가하여 동일하게 수행하십시오.

(defun my-union (a b &aux (res (list 1)) (p res)) 
    (nadd-elts p a) 
    (nadd-elts p b) 
    (cdr res)) 

nadd-elts

는 파괴적 예를 들어, 사용 ( p가 가리키는)의 마지막 셀을 업데이트 목록의 마지막에 추가합니다 rplacd. 예를 들어 here입니다.

는 nadd-elts가 flattening 절차를 emulate 것, 요소를 추가하고, 중복 res 확인 후 p에 각 잎 요소를 추가합니다.

---

파괴 갱신하지 않고, 기능적인 스타일에서 작업은 일반적인 접근 방식은 동일하게 유지 : 그것으로 첫 번째 목록을 추가, 빈 결과 목록에서 시작 - 중복없이 - 다음 두 번째.

(defun my-union (a b &aux res) 
    (setq res (add-into res a)) 
    (setq res (add-into res b)) 
    res) 

이제는 add-into 기능을 구현했습니다.

(defun add-into (res a &aux r1 r2) 
    (cond 
    ((atom a) ....) 
    (T (setq r1 (add-into res (car a))) 
     (setq r2 (............ (cdr a))) 
     r2))) 

은 상기 보조 변수없이 set 프리미티브 안에 재 작성 될 수있다. 확인을 여기에 내가 그 무슨 뜻인지 얼마나 ... 알아보십시오 :

당신이 해시 테이블을 사용하는 것이 허용되지 않는 한 (어떤 이유로 내가 전에 요구 사항으로이 발생했습니다)

(defun my-union (a b) (add-into NIL (cons a b))) 

(defun add-into (res a) 
    (cond 
    ((atom a) ....) 
    (T (add-into (add-into res (car a)) 
        (cdr a))))) 

Answer 3

, 당신이 올 수 결과 집합을 만드는 데 도움이되는 순서 지정 함수를 사용하면 검색을 반복해서 반복 할 필요가 없습니다.

또한 중첩 목록이 허용되므로 트리에서 중복 된 항목 만 제거하도록 문제가 확장됩니다. 처리하기 전에 원하는만큼 많은 목록을 추가 할 수 있습니다.

지금, 나는 당신이 그것을 할 수있는 방법의 몇 가지 예를 보여주기 위해 노력할 것이다 : 나는 요소를 주문하는 데 사용했다 함수가 보편적 아니라고

가

;; Large difference between best and worst case. 
;; Lists containing all the same items will be processed 
;; in square time 
(defun union-naive (list &rest lists) 
    (when lists (setf list (append list lists))) 
    (let (result) 
    (labels ((%union-naive (tree) 
       (if (consp tree) 
        (progn 
        (%union-naive (car tree)) 
        (when (cdr tree) (%union-naive (cdr tree)))) 
        (unless (member tree result) 
        (setq result (cons tree result)))))) 
     (%union-naive list) result))) 

;; Perhaps the best solution, it is practically linear time 
(defun union-hash (list &rest lists) 
    (when lists (setf list (append list lists))) 
    (let ((hash (make-hash-table)) result) 
    (labels ((%union-hash (tree) 
       (if (consp tree) 
        (progn 
        (%union-hash (car tree)) 
        (when (cdr tree) (%union-hash (cdr tree)))) 
        (setf (gethash tree hash) t)))) 
     (%union-hash list)) 
    (maphash 
    #'(lambda (a b) 
     (declare (ignore b)) 
     (push a result)) hash) 
    result)) 

;; This will do the job in more time, then the 
;; solution with the hash-map, but it requires 
;; significantly less memory. Memory is, in fact 
;; a more precious resource some times, but you 
;; have to decide what algo to use based on the 
;; data size 
(defun union-flatten (list &rest lists) 
    (when lists (setf list (append list lists))) 
    (labels ((%flatten (tree) 
      (if (consp tree) 
       (if (cdr tree) 
        (nconc (%flatten (car tree)) 
          (%flatten (cdr tree))) 
        (%flatten (car tree))) 
       (list tree)))) 
    ;; the code below is trying to do something 
    ;; that you could've done using 
    ;; (remove-duplicates (%flatten list)) 
    ;; however sorting and then removing duplicates 
    ;; may prove to be more efficient 
    (reduce 
    #'(lambda (a b) 
     (cond 
      ((atom a) (list a)) 
      ((eql (car a) b) b) 
      (t (cons b a)))) 
    (sort (%flatten list) 
      #'(lambda (a b) 
       (string< (symbol-name a) 
         (symbol-name b))))))) 



(union-naive '(((a))) '(b(c((d e))a))) 
(union-hash '(((a))) '(b(c((d e))a))) 
(union-flatten '(((a))) '(b(c((d e))a))) 

공지 사항,하지만 당신은 아마 할 수있을 것입니다 모든 종류의 데이터에 대한 대체 기능을 제안하십시오. 일반적으로 빠른 해싱 함수를 사용하면 간단하게 해왔습니다. 커먼 리스프에서

:이 첫 번째 숙제이며, 당신이 리스프에 새로운 때문에