在Lisp中反转列表

Question

我试图在Lisp中反转列表,但是我得到错误:"错误:异常C0000005 [标志0]在20303FF3 {偏移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

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

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 '(1 2) '(ab) '(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)

也就是说，与其使用外部辅助函数，不如使用标签来定义本地辅助函数：

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