1

在 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)
4

4 回答 4

2

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

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

当然，您可以自己编写一个函数来将值“附加”到列表中，并返回一个新值：

(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列表的长度有关。

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

另请参阅append已经是 Common Lisp 一部分的函数。

为了给你一个概述，你可以

  • 以“错误”顺序（使用cons）收集值，然后破坏性地反转该列表（nreverse）
  • 以“错误”的顺序收集值，然后创建一个新的反向列表，其中的值以正确的顺序 ( reverse)
  • 实际上append你的值到列表中，容忍可能的二次或更差的运行时间。
  • 实际上将您的值附加到列表中，破坏性地修改列表结构（nconc）。这是一个改进，append因为您不需要分配大量新的 cons 单元，但您仍然存在运行时问题。

基于uselpa的“hack”，我编写了使用这种“列表”进行操作的函数。它由一个 cons 组成，它car指向列表（即列表）的开头，并且cdr指向列表的最后一个 cons 单元格。尽管最后一个单元格始终是(nil . nil)，但简化了附加值：

首先，将car最后一个单元格的 设置为新值，然后将 设置cdr为一个新的单元格(nil . nil)，最后返回那个新的“列表”：

(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)))
于 2015-11-12T21:05:59.770 回答
2

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

? (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。

于 2015-11-12T21:11:22.733 回答
2

Lisp 列表是单链表。真的，没有这样的“列表”，只有一堆 cons-cells，也称为对，我们按照惯例将其解释为列表。 (cons xy)产生一对(x . y)。作为一种特殊情况，当 cons 的 cdr 是一个列表时，例如，在(x . (1 2 3))中，我们将该对写为(x 1 2 3)。并且符号nil是空列表，所以(x . nil)是(x)。所以，有了缺点，你所能做的就是创建一个新的配对。如果您有一个现有列表l = (abc...)和一个新元素e，您可以创建列表(eabc...)，您已经完成了，或者您可以创建新列表((abc...) e)，这并不是您真正想要的。

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

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

并且您将nil替换为( d)，以获得(abcd)。这需要使用setf而不是setq，因为setq只能修改变量，而不是任意位置（如 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))))
于 2015-11-12T21:27:14.113 回答
0

通常的习语要么使用:collect扩展的功能，要么loop通过推动（如您所描述的）并在最后反转来积累。

例如，下面是一个简单range函数的两个版本，它返回 n 以下从 0 开始的整数：

(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))))
于 2015-11-13T09:02:50.173 回答