lisp - Lisp 中的反转列表

Question

我正在尝试反转 Lisp 中的列表，但出现错误:“错误:20303FF3 处的异常 C0000005 [标志 0] {内部偏移量 25#}eax 108 ebx 200925CA ecx 200 edx 2EFDD4Desp 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 函数生成除最后一个参数以外的所有参数的副本。例如，当您执行 (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，因为它更清楚地表明我们正在处理列表，而不是任意的 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)))