lisp - 创建自定义列表反转

Question

我正在尝试在 Lisp 中创建列表的自定义反转。我是 Lisp 编程的新手，仍在语法上苦苦挣扎。到目前为止，这是我的代码

(defun new-union(l1 l2)
    (setq l (union l1 l2))
       (let (res) 
         (loop for x in l
           do(setq res (cons (car l) res))
           do(setq l (cdr l)))))

这里我取两个列表，并形成联合列表l。然后为了反转列表 l，我访问元素明智的将其附加到新列表 res。然后使用 cons、car 和 cdr 来更新列表。但是，我得到了一个奇怪的输出。有人可以建议我哪里出错了吗？

我知道有一个名为 nreverse 的内置函数，但我想尝试看看 Lisp 如何解释列表中的数据。

关于最后打印res，例如

(new-union '(a b c) '(d e f))

上面调用的输出给了我

(L A A A A A A A X X)

我想我的循环是错误的。

Answer 1

问题

(之前评论的总结)

1. 错误的缩进、空格和名称；更喜欢这个:

   (defun new-union (l1 l2)
     (setq list (union l1 l2))
     (let (reversed) 
       (loop for x in list
             do (setq res (cons (car list) reversed))
             do (setq list (cdr list)))))
   

2. 在未声明的全局变量上使用 SETQ，而不是 LET

3. 正在迭代的结构的突变 (LIST)
4. 不在 LOOP 中使用 X(为什么要定义它？)
5. 返回值总是NIL

重构

(defun new-union (l1 l2)
  (let ((reverse))
    (dolist (elt (union l1 l2) reverse)
      (push elt reverse))))

• 定义一个本地reverse变量，默认绑定(bind)到NIL(你可以将它设置为'()，这有时是首选)。
• 使用DOLIST 遍历列表并执行副作用；第三个参数是返回值；在这里你可以把 reverse 变量放在我们累积反转列表的地方。
• 对于每个元素elt，将其推到reverse的前面；如果您想避免出于学习目的使用 push，请使用 (setf reverse (cons elt reverse))。

Common Lisp 是多范式并且支持务实的解决方案:有时循环更自然或更高效，没有理由强制自己采用函数式风格。

功能实现

然而，列表提供了一种自然的归纳结构:递归方法在某些情况下可能更合适。如果您想使用函数式风格进行逆向计算，请注意尾调用优化虽然普遍可用，但并不是语言规范所要求的(这取决于您的实现能力和编译器选项)。

在默认设置下，SBCL 消除了尾部位置的调用，并消除了大输入时堆栈溢出的风险。但是如果你不小心的话，还有其他可能的方法来获得糟糕的算法复杂性(和浪费的代码)。以下是我用来定义 union 和 reverse 组合的内容；特别是，我更喜欢使用 labels 定义本地函数，以避免使用虚拟 nil 参数调用 new-union。此外，我只迭代一次联合生成的列表。

(defun new-union (l1 l2)
  (labels ((rev (list acc)
             (etypecase list
               (null acc)
               (cons (rev (rest list)
                          (cons (first list) acc))))))
    (rev (union l1 l2) nil)))

跟踪

  0: (NEW-UNION (A B C) (D E F))
    1: (UNION (A B C) (D E F))
    1: UNION returned (C B A D E F)
    1: (REV (C B A D E F) NIL)
      2: (REV (B A D E F) (C))
        3: (REV (A D E F) (B C))
          4: (REV (D E F) (A B C))
            5: (REV (E F) (D A B C))
              6: (REV (F) (E D A B C))
                7: (REV NIL (F E D A B C))
                7: REV returned (F E D A B C)
              6: REV returned (F E D A B C)
            5: REV returned (F E D A B C)
          4: REV returned (F E D A B C)
        3: REV returned (F E D A B C)
      2: REV returned (F E D A B C)
    1: REV returned (F E D A B C)
  0: NEW-UNION returned (F E D A B C)

备注

反转union的结果还是挺让人意外的，当并集应该对无序集进行操作时:结果中元素的顺序不必以任何方式反射(reflect) list-1 或 list-2 的顺序。集是无序集合，具有没有重复；如果您的输入列表已经表示集合，正如函数名称 (new-union) 所暗示的那样，则删除重复项或期望顺序有意义是没有意义的。

相反，如果输入列表表示值序列，那么顺序很重要；可以随意将 append 或 concatenate 与 remove-duplicates 结合使用，但请注意，后者默认会删除列表前面的元素:

(remove-duplicates (concatenate 'list '(4 5 6) '(2 3 4)))
=> (5 6 2 3 4)

您可能想改用 :from-end t。