1

需要在 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)))

我的错误是段中有一个“非法函数对象”（null（member（car i）lst3））

建议？

4

4 回答 4

1

该错误是因为您正在尝试执行评估的结果(null (member (car i) lst3))。在您的cond表达式中，如果i是一个列表，那么它会尝试评估该表达式

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

并返回结果。表达式中的第一个元素应该是一个函数，但是

(null (member (car i) lst3))

将返回一个布尔值。因此失败。您的代码结构需要注意。你错过的是你需要一个内在的cond，那里。

顺便说一句，如果您递归地执行它，这将是一个更清洁的功能。

我是一个计划者而不是一个 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)))

（编辑以纠正倒数第二行中的简单输入错误，感谢 Will Ness 发现它）

于 2012-10-11T23:46:57.303 回答
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在需要的地方添加了一些 s：

(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)会复制 中的顶级 cons 单元格lst3，这完全是多余的。

您那里的长语句通常放在正文中，而不是放在局部变量do的更新表单中。do

do但是您可以在适当的情况下使用更专业的 形式。这里很自然地使用dolist. 遵循“wvxvw”关于使用哈希表进行成员资格测试的指导，我们写道：

(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单元格。

于 2012-10-13T19:57:08.277 回答
0 
(remove-duplicates (append '(a b c) '(e c d)) :from-end t)
于 2012-10-11T21:39:16.503 回答
0

因为您从 开始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))))
于 2012-10-12T16:54:23.967 回答