如何仅使用 cons 将值附加到现有列表？

Question

在 lisp 中，我尝试仅使用基本函数将值附加到列表：setq cons car 和 cdr。

我可以反向创建列表，但我很难弄清楚如何按顺序推送它们，如何做到这一点？

(setq list NIL)
(setq list (cons 1 list))
(setq list (cons 2 list))
(setq list (cons 3 list))

Result:
(3 2 1)

Answer 1

这是一个令人惊讶的广泛话题。首先，通常情况下，您不会将单个项目附加到列表中。处理您可能遇到的这种情况的通常方法是，首先将需要的值收集到一个列表中，然后反转该列表以获得正确的顺序：

(let ((my-list '()))
  (dotimes (i 10)
    (setf my-list (cons i my-list)))
  (nreverse my-list)) ; NOTE: nreverse destructively modifies its argument
;;=> (0 1 2 3 4 5 6 7 8 9)

当然你可以自己写一个函数来"append"一个列表的值，返回一个新值：

(defun my-append (value list)
  (if (null list)
      (cons value '()) ; or use (list value)
      (cons (first list) (my-append value (rest list)))))

您可以将其转换为尾递归变体，但这并不能解决此函数的主要问题：它需要遍历整个列表以追加每个元素。因此，这在 O(n) 中，n 是列表的长度。

另一个问题是这个函数 consing 很多，也就是说它会产生很多额外的 cons cells，导致内存管理的大量工作。不过，可以通过破坏性地修改其参数来解决这个问题。

另请参阅已成为 Common Lisp 一部分的函数 append。

为了给您一个概览，您可以

收集 "wrong" 顺序中的值（使用 cons），然后破坏性地反转该列表 (nreverse)
收集 "wrong" 顺序的值，然后创建一个新的反向列表，其中值的顺序正确 (reverse)
实际上 append 您的值在列表中，容忍可能的二次方或更糟的运行时间。
实际上是将您的值附加到列表中，破坏性地修改列表结构 (nconc)。这是对 append 的改进，因为你不需要分配很多新的缺点单元格，但你仍然有运行时间问题。

基于uselpa的"hack"我编写了函数来操作这样的"list"。它由一个 cons 组成，其 car 指向列表（即列表）的开头，其 cdr 指向列表的最后一个 cons 单元格。虽然最后一个单元格始终是 (nil . nil)，但简化附加值：

首先，将最后一个单元格的 car 设置为新值，然后将 cdr 设置为新单元格 (nil . nil)，最后 returns新 "list":

(defun empty-al ()
  (let ((cell (cons nil nil)))
    (cons cell cell)))
(defun cons-al (value al)
  (cons (cons value (car al))
        (cdr al)))
(defun append-al (value al)
  (let ((new-cell (cons nil nil)))
    (setf (cadr al) value
          (cddr al) new-cell)
    (cons (car al) new-cell)))

Answer 2

有一种技术（我不记得它是否有具体名称）包括创建一个具有任何 car 值的初始 cons 单元并保持指向 cdr 的指针。然后追加包括 setfing 指针的 cdr 和推进指针。您想要的列表随时都是初始 cons 单元格的 cdr：

? (progn (setq lst (cons 'head nil)) (setq lst-p lst) (cdr lst))
NIL
? (progn (setf (cdr lst-p) (cons 1 nil)) (setq lst-p (cdr lst-p)) (cdr lst))
(1)
? (progn (setf (cdr lst-p) (cons 2 nil)) (setq lst-p (cdr lst-p)) (cdr lst))
(1 2)
? (progn (setf (cdr lst-p) (cons 3 nil)) (setq lst-p (cdr lst-p)) (cdr lst))
(1 2 3)

所以这只使用了 setq、cons、cdr，还有 setf.

Answer 3

Lisp 列表是单链表。实际上，没有 "list" 本身，只有一堆 cons-cells，也称为对，我们按照惯例将其解释为列表。 (cons x y) 生成一对 (x . y)。作为一种特殊情况，当 cons 的 cdr 是一个列表时，例如，在 (x . (1 2 3)) 中，我们将这对写为 (x 1 2 3)。而符号 nil 是空列表，所以 (x . nil) 是 (x)。因此，如果有缺点，您所能做的就是创建一对新的。如果您有一个现有列表，l = (a b c…)，以及一个新元素，e ，您可以创建您已经完成的列表 (e a b c…)，或者您可以创建新列表 ((a b c…) e)，这不是你真正想要的。

要修改列表的 tail，您需要能够更新现有 cons 单元格的 cdr。例如，如果您有 (a b c)，在非 shorthand 形式中，它是 (a . (b . (c . nil))) ，你可以这样做：

(setf (cdr (cdr (cdr the-list))) (list 'd))

然后您将替换 nil 为 (d)，得到 (a b c d)。那需要使用setf，而不是setq，因为setq只能修改变量，不能任意修改places（比如 cons 单元格的 cdr）。

从习惯上讲，如果您以相反的顺序获取所需的项目，那么反向创建列表是一种常见的习惯用法，就像您正在做的（或使用推送等），然后最后反转。例如，这是单列表版本的 mapcar 的样子：

(defun mapkar (function list)
  "A simple variant of MAPCAR that only takes one LIST argument."
  ;; On each iteration, pop an element off of LIST, call FUNCTION with
  ;; it, and PUSH the result onto the RESULTS list.  Then,
  ;; destructively reverse the RESULTS list (it's OK to destructively
  ;; modify it, since the structure was created here), and return it.
  (let ((results '()))
    (dolist (x list (nreverse results))
      (push (funcall function x) results)))

这是同一事物的尾递归版本：

(defun mapkar (function list &optional (result '()))
  (if (endp list)
      (nreverse result)
      (mapkar function
              (rest list)
              (cons (funcall function (first list))
                    result))))

Answer 4

通常的习语要么使用扩展loop的:collect特性，要么通过推动（如您所述）积累并最终反转。

例如，这里有两个版本的简单 range 函数，returns 从 0 开始的整数 n:

(defun range (n)
  (loop :for i :below n
        :collect i))

(defun range (n)
  (let ((list ()))
    (dotimes (i n)
      (push i list))
    (reverse list)))

根据您提到的限制，我建议实施您自己的 reverse 并使用它。这是一个尾递归示例，但请注意，您的 Lisp 实现不需要支持尾递归。

(defun own-reverse (list &optional (acc ()))
  (if (endp list)
      acc
      (own-reverse (rest list)
                   (cons (first list) acc))))

如何仅使用 cons 将值附加到现有列表？

How do I append values in order to an existing list using only cons?

lisp

common-lisp

cons