这个 Common Lisp 代码是否与 Winston / Horn 在 LISP 第 3 版中教授的代码相似/相同？

Question

他们是这么说的

(defun user-reverse (l)
  (if (endp l)
      nil
      (append (user-reverse (rest l))
              (list (first l)))))

由于计算量为 n(n + 1)/2，所以不好。

然后他们说往这边走:

(defun user-reverse (l &optional result)
  (if (endp l)
      result
      (user-reverse (rest l)
                    (cons (first l) result))))

所以我在想，为什么你不能做这样的事情呢:

(defun user-reverse (l)
  (do ((new-list nil))
      ((endp l) new-list)
    (push (pop l) new-list)))

这是坏习惯还是什么？或者它是否复制列表或其他内容？他们教了 'DO' 几章，想知道是否有任何 LISPers 可以说这是否与他们的榜样相提并论或更糟？基本上，想知道他们的坏 'n' 例子是如何站起来的？

Answer 1

有两个问题：

算法和数据结构的复杂性和效率
递归与循环

我们先来看complexity/efficiency问题

Lisp 中的列表是cons单元的单链表或空列表。因此，简单地附加到列表的末尾是一项代价高昂的操作。在 Lisp 列表中，将元素添加到列表的前面成本低，而添加到列表末尾的成本高。因此，应该编写一个例程，使其不使用这些昂贵的操作。

如果我们有一个像第一个使用代价高昂的追加操作的递归例程，我们想找到一个不同的例程，它不会添加到列表的末尾。这就是为什么第二个套路比第一个好。

递归与循环

您发布的第二个版本是结束递归。递归调用可以用两个变量的跳转和更新来代替。这使用 尾调用优化 (TCO)。在 Lisp 中，这是一种优化，编译器通常可以做到这一点。但他们不需要这样做，基于解释器的实现通常不需要。在 Scheme 中，语言定义要求实现支持 TCO。

对于 TCO，第二个版本既使用高效操作又以常量运行 space（不过它分配了一个反向列表）。

在没有 TCO 的情况下，第二个版本使用高效的操作，但可能会导致大型列表的堆栈溢出。

循环

第三个版本使用循环 - 此处 DO。它既使用高效的运算符，又仅受内存大小的限制。它不受堆栈大小的限制，因为它不进行任何递归调用。

通常在 Lisp 中的实际软件（-> 不是为教学目的而编写）中，人们会发现使用循环的代码，因为 TCO 并非在所有实现中通常都可用。例如，Common Lisp 的 ABCL 实现在 Java 虚拟机 (JVM) 上运行。由于 JVM 不提供实现 TCO 的直接功能，因此 JVM 的编程语言实现通常不提供 TCO。 ABCL也不例外。

dolist

循环版可以写成dolist:

(defun user-reverse (l &aux r)
  (dolist (e l r)
    (push e r)))

这个 Common Lisp 代码是否与 Winston / Horn 在 LISP 第 3 版中教授的代码相似/相同？

Is this Common Lisp code similar / equal to what they're teaching in LISP 3rd Edition by Winston / Horn?

lisp

reverse

list

common-lisp

time-complexity