Lisp Cons Cell是什么定义？

Question

什么是Common Lisp Cons Cell的定义？ Cons Cell和标准链表项有何不同？毕竟，Cons Cell和链表项都有一个值和指向下一个单元格或项的指针...这个理解是错误的吗？

- λ Jonas Gorauskas

---

每个列表（除了nil）都是一个cons单元，但不是每个cons单元都是一个列表（如果它的cdr不是一个列表）。 - mihi

我只是想澄清一下，我正在比较Common Lisp列表及其Cons单元与像C、C++或Java这样的语言中实现的常规链表及其项之间的区别。 - λ Jonas Gorauskas

Answer 1

Cons单元通常包含两个指针，可以指向任何东西。通常的用法是使用左侧指针指向“值”，使用右侧指针指向另一个Cons单元（或nil）。

- Zed

---

Cons单元也可以直接保存值，而不必保存指针。使用(cons 1 2)创建的Cons单元将具有指向数字的指针，但可以直接存储它们(对于某些其他小项目如字符也是如此)。 - Rainer Joswig

Answer 2

Cons单元格更接近于二叉树节点而非链表节点。car和cdr返回两个子节点，它们可以是nil、原子或其他cons单元格。

- Jim Lewis

---

强调这里的区别，第二个元素并不必须是另一个 cons cell。('tofu . 1)是一个合法的 cons cell。 - Chuck

Answer 3

一个cons单元是由cons、car和cdr组成的合同的三分之一，要求它们像对一样运作，正如其他人所提到的那样。

从这个定义中省略“引用”、“指针”等词语的原因是为了认识到这些是实现细节。如果你想的话，你可以像Abelson和Sussman一样从空气中构建一个cons。

(define (cons a b) (lambda (x) (x a b)))
(define (car x) (x (lambda (a b) a)))
(define (cdr x) (x (lambda (a b) b)))

这个定义完全存在于Lisp的定义和函数世界中，甚至没有考虑对象是存储为值还是引用; 然而它们可以作为原始对象的替代品（不考虑可变性或其他特殊用途）。

- Josh Lee

Answer 4

在Lisp中，cons单元格保存一对值。如果cons单元格在变量c中，则(car c)返回第一个值，(cdr c)返回第二个值。

按照惯例，列表由cons单元格组成，其中单元格的car包含节点值，cdr包含对下一个节点或nil（空列表）的引用，以表示列表的结尾。当原始函数返回或接受列表时，这是列表呈现的格式。

因此，对于列表l，(car l)给出第一个元素（第一个cons单元格中的值），(cdr l)返回列表的尾部（列表中的下一个cons单元格）。

- ReWrite

Answer 5

我认为其他回答虽然准确，但没有明确一件事。

在传统的C++链表实现中，两个字段（比如说val和next）是有类型的。 next 被定义为指向列表中的另一个节点，null 是终止符。你不能使用 next 指向除了另一个节点以外的任何东西。

Lisp 是动态类型的，因此 cons 单元格中的任何字段都可以是任何东西（原子或引用）。您可以使用 cons 单元格实现链表（这就是 Lisp 列表的全部内容：带有 nil 终止符的 cons 单元格链），但您也可以在每个字段中放置任意值，例如使用 cons 单元格作为坐标对、树节点等等。

您甚至可以将它们组合起来；例如，x y 坐标的列表：

;; (cons foo (cons bar nil)) == (list foo bar)    
(cons
  (cons 5 4)
  (cons (cons 9 10) nil))
=>
((5 . 4) (9 . 10))

一个cons单元比一个链表节点更加通用，可以说它更接近于一个“应用对”。所有标准的列表处理函数（map、dolist等）都是假设你将值放在car中，另一个列表放在cdr中的函数。

这意味着——如果你愿意的话——你可以反向定义列表，即car指向下一个cons单元，cdr指向值！如果要使用链表节点来实现这个功能，则需要重新定义类或数据结构以更改类型。

- Rich