Lisp 中的反转列表

Question

我正在尝试反转 Lisp 中的列表，但出现错误：“错误：20303FF3 处的异常 C0000005 [标志 0] {内部偏移量 25#} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 "

我的代码如下：

(defun rev (l)
    (cond
        ((null l) '())
        (T (append (rev (cdr l)) (list (car l))))))

谁能告诉我我做错了什么？提前致谢！

Answer 1

在 ANSI Common Lisp 中，您可以使用 reverse 函数反转列表（非破坏性：分配一个新列表），或 nreverse（将现有列表的构建块或数据重新排列为产生相反的那个）。

> (reverse '(1 2 3))
(3 2 1)

不要在引用列表文字上使用 nreverse；它是未定义的行为，可能会以令人惊讶的方式表现，因为它是事实上自修改代码。

Answer 2

如果你可以使用标准的 CL 库函数，如 append, you should use reverse (as )。

否则，如果这是一个练习（h/w或不是），你可以试试这个：

(defun rev (l)
  (labels ((r (todo)
             (if todo
                 (multiple-value-bind (res-head res-tail) (r (cdr todo))
                   (if res-head
                       (setf (cdr res-tail) (list (car todo))
                             res-tail (cdr res-tail))
                       (setq res-head (list (car todo))
                             res-tail res-head))
                   (values res-head res-tail))
                 (values nil nil))))
    (values (r l))))

PS。您的具体错误无法理解，请联系您的供应商。

Answer 3

您编写的代码在逻辑上是正确的，并且会产生您想要的结果：

CL-USER> (defun rev (l)
           (cond
             ((null l) '())
             (T (append (rev (cdr l)) (list (car l)))))) 
REV
CL-USER> (rev '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev '())
NIL
CL-USER> (rev '(1 2))
(2 1)

也就是说，它在性能方面存在一些问题。 append 函数生成除最后一个参数之外的所有参数的副本。例如，当您执行 (append '(1 2) '(a b) '(3 4)) 时，您将创建四个新的 cons 单元，其汽车分别为 1、2、 a 和 b。最后一个的cdr是现有的列表（3 4）。那是因为 append 的实现是这样的：

(defun append (l1 l2)
  (if (null l1)
      l2
      (cons (first l1)
            (append (rest l1)
                    l2))))

这不完全是 Common Lisp 的 append，因为 Common Lisp 的 append 可以接受两个以上的参数。不过，这足以证明为什么除了最后一个列表之外的所有列表都被复制了。现在看看这对 rev 的实现意味着什么：

(defun rev (l)
  (cond
    ((null l) '())
    (T (append (rev (cdr l)) (list (car l))))))

这意味着当您反转 (1 2 3 4) 这样的列表时，就像您是：

(append '(4 3 2) '(1))              ; as a result of    (1)
(append (append '(4 3) '(2)) '(1))  ; and so on...      (2)

现在，在第 (2) 行中，您正在复制列表 (4 3)。在第一行中，您正在复制列表 (4 3 2)，其中包括 (4 3) 的副本。也就是说，您正在复制一个副本。这是对内存的一种相当浪费的使用。

更常见的方法是使用累加器变量和辅助函数。（请注意，我使用 endp、rest、first 和 list* 而不是 null、cdr、car 和 cons，因为它更清楚地表明我们正在使用列表，而不是任意的缺点树。它们几乎相同（但有一些差异）。）

(defun rev-helper (list reversed)
  "A helper function for reversing a list.  Returns a new list
containing the elements of LIST in reverse order, followed by the
elements in REVERSED.  (So, when REVERSED is the empty list, returns
exactly a reversed copy of LIST.)"
  (if (endp list)
      reversed
      (rev-helper (rest list)
                  (list* (first list)
                         reversed))))

CL-USER> (rev-helper '(1 2 3) '(4 5))
(3 2 1 4 5)
CL-USER> (rev-helper '(1 2 3) '())
(3 2 1)

有了这个辅助函数，很容易定义 rev:

(defun rev (list)
  "Returns a new list containing the elements of LIST in reverse
order."
  (rev-helper list '()))

CL-USER> (rev '(1 2 3))
(3 2 1)

也就是说，与其使用外部辅助函数，不如使用 labels 定义局部辅助函数更常见：

(defun rev (list)
  (labels ((rev-helper (list reversed)
             #| ... |#))
    (rev-helper list '())))

或者，由于 Common Lisp 不能保证优化尾部调用，do 循环在这里也很干净：

(defun rev (list)
  (do ((list list (rest list))
       (reversed '() (list* (first list) reversed)))
      ((endp list) reversed)))

Answer 4

您可能运行出栈 space；这是在尾部位置之外调用递归函数 rev 的结果。转换为尾递归函数的方法涉及引入累加器，变量result如下：

(defun reving (list result)
  (cond ((consp list) (reving (cdr list) (cons (car list) result)))
        ((null list) result)
        (t (cons list result))))

你的 rev 函数就变成了：

(define rev (list) (reving list '()))

示例：

* (reving '(1 2 3) '())
(3 2 1)
* (reving '(1 2 . 3) '())
(3 2 1)

* (reving '1 '())
(1)

Lisp 中的反转列表

reversing list in Lisp

lisp

flags

common-lisp