lisp - 稳定联合 lisp

Question

需要在 lisp 中编写一个联合函数，它将两个列表作为参数并返回一个列表，该列表是两个列表的并集，没有重复。顺序应与输入列表的顺序一致

例如:如果输入是'(a b c)和'(e c d)，结果应该是'(a b c e d)

这是我目前的情况

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

我的错误是存在一个“非法函数对象”，段为 (null (member (car i) lst3))

建议？

Answer 1

你把你的 parent 弄得一团糟:

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

使用一种我称之为“head-sentinel”的技术(z 变量预初始化为单例列表)允许以一定的成本极大地简化自上而下列表构建的代码分配一个额外的 cons 单元格。