创建自定义列表反转

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

好的......我想你想要两个列表，将它们组合在一起，删除重复项，然后反转它们。

您最大的问题是您使用的是循环而不是递归。 LISP 的诞生就是为了使用递归来进行列表处理。自然多了。

下面是一个非常简单的示例：

(defvar l1 '(a b c))      ;first list
(defvar l2 '(d e f))      ;second list

(defun my-reverse (a b)   ;a and b are lists
  "combines a and b into lst, removes duplicates, and reverses using recursion"
  (let ((lst (remove-duplicates (append a b))))   
    (if (> (length lst) 0)
        (append (last lst) (my-reverse nil (butlast lst)))
        nil)))

使用 SBCL 在 SLIME 中编译的示例运行

; compilation finished in 0:00:00.010                                                                                                                                    
CL-USER> l1 ;; verify l1 variable
(A B C)                                                                                                                                                                  
CL-USER> l2 ;; verify l2 variable
(D E F)                                                                                                                                                                  
CL-USER> (append l1 l2) ;; append l1 and l2
(A B C D E F)                                                                                                                                                            
CL-USER> (my-reverse l1 l2) ;; reverse l1 and l2
(F E D C B A)

Answer 2

问题

（之前评论的总结）

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

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

在未声明的全局变量上使用 SETQ，而不是 LET
正在迭代的结构的突变 (LIST)
不在 LOOP 中使用 X（为什么要定义它？）
return 值始终为 NIL

重构

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

定义一个本地reverse变量，默认绑定到NIL（你可以将它设置为'()，有时这是首选）。
使用DOLIST遍历列表并执行副作用；第三个参数是 return 值；在这里你可以把 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 的结果是相当令人惊讶的：结果中元素的顺序不必反映顺序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。

创建自定义列表反转

Creating a custom reverse of list

lisp

clisp

common-lisp

问题

重构

功能实现

追踪

备注