stable-union lisp

Question

需要在lisp中編寫一個聯合函數，它將兩個列表作爲參數並返回一個列表，該列表是沒有重複的兩個列表的聯合。爲了應與輸入的一致列出

例如：如果輸入的是「（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))) 

這裏是你的代碼，你可能想要它是與修正的括號，並增加了一些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))的結果。在您的COND表達，如果我是一個列表，然後它會嘗試計算表達式

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

，並返回結果。在表達式中的第一個元素應該是一個函數，但

(null (member (car i) lst3)) 

會返回一個布爾值。因此失敗。你的代碼結構需要注意。你錯過的是，你需要一個內在的條件是，那裏。

順便說一句，如果你遞歸地做了這個，它將是一個更乾淨的函數。

我是一個Schemer而不是Lisper，但我有點想一想。這裏是一個遞歸實現的骨架：

(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))) 

（編輯以簡單tyop在倒數第二行，感謝威爾內斯爲察覺它）

Answer 4

因爲你do開始時，因爲遞歸解決辦法是更糟的是，這裏是你可以做了什麼：

(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))))