[科普中国]-列表构造函数

列表构造函数是用来构造列表的基本函数，在大多数 LISP 体系的计算机编程语言中，使用的函数名称是cons。

cons构成了存放两个变量与其指针的内存物件，这个物件被称为（cons）单元、非原子的 S 表达式或（cons 对）。LISP 编程中表达要把 x 加入 y 的语法：(cons x y)，构造了一个新物件。产生的结果具备了左半部，称为car（第一元素或暂存器位址的内容）；以及右半部称为cdr（其余元素或递减暂存器的内容）。

使用虽然cons单元可用于储存有序的数据对，但它们更常用于组合为更复杂的复合数据结构，特别是列表和二叉树。1

有序对例如 LISP 表达式(cons 1 2)产生一个有序的单元，在左半部存放 1，而右半部存放 2 。
左右次序不能互换（(1 2)跟(2 1)不同）。在 LISP 表示法中，(cons 1 2)结果会印出如下：

(1 . 2)须注意 1 和 2 之间的句点；这个 S 表达式是特殊的“点对”（所谓的cons对），并不是普通的“列表”。

列表列表(42 69 613)的 Cons单元图，以cons构造函数写成：

(cons 42 (cons 69 (cons 613 nil)))此外可用list函数写成：

(list 42 69 613)LISP 编程中的列表实作在cons对之上。具体地说，每个列表的结构都是：

一个空列表()，通常被称为nil的特殊物件。

一个cons单元，car代表这列表的第一个元素，而cdr则是包含其余元素的一个子列表。

这形成了简单基本的列表，而cons，car和cdr函数可以操作列表的内容。
注意，nil是个特殊的空列表，并不是cons对。考虑元素为 1,2 和 3 的列表为例。
这样的列表经由三个步骤产生：

CONS3 到nil空列表之上

CONS2 到上一步的结果之上

CONS1 到上一步的结果，产生最后的结果

这相当于单一表达式：

(cons 1 (cons 2 (cons 3 nil)))或可用list函数节略如下：

(list 1 2 3)最终结果是一个列表，形式如右：(1 . (2 . (3 . nil)))

因此cons操作会在既有列表的最前头，添加一个元素。例如，如果x是上面定义的列表，
那么(cons 5 x)将产生列表：(5 1 2 3)。另一个有用的函数是append， 用于合并两个列表。

Use in conversation与指令式编程中使用的类型的破坏性操作不同，相反地 CONS 函数可以参考成内存分配的一般过程。例如： I sped up the code a bit by putting in side effects instead of having it cons like crazy.

函数式实作由于 LISP 具有一阶函数，所以所有数据结构，包括 cons 单元，都可以使用函数实现。例如，在 Scheme 中：

(define (cons x y) (lambda (m) (m x y)))(define (car z) (z (lambda (p q) p)))(define (cdr z) (z (lambda (p q) q)))这种技术被称为邱奇编码。它重新实现cons，car 和cdr 操作，使用一个函数作为 “cons cell”。邱奇编码是一种常用的方法，在纯λ演算中定义数据结构，抽象的理论计算模型与 Scheme 密切相关。这种实现虽然在学术上是有趣的，但不切实际，因为它使得单元与任何其他方案过程不可区分，以及引入不必要的计算低效。然而，相同种类的编码可以用于具有变体的更复杂的代数数据类型，其中它甚至可能变得比其他类型的编码更有效。这种编码还具有可以在不具有变体的静态类型语言（例如 Java）中实现的优点，使用接口而不是 lambdas。2

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学