Lisp 函数 : union

Question

我有一个口齿不清的家庭作业，我很难处理它。

我必须编写一个执行联合操作的函数。该函数采用原子或列表形式的 2 个输入，并合并每个元素，保留顺序并去除所有级别的括号。

函数的输出:

(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

因为这是你的第一份作业，而且你是 Lisp 的新手，这里有一个非常简单的自上而下的方法，不用担心性能，并充分利用 CL 提供的工具:

在Common Lisp中，已经有一个删除重复项的函数: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)