列表构造函数

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

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

以上约略地和面向对象的构造器概念相关，即产生一个给定参数的新物件，而其与代数数据类型系统的构造函数，有更密切相关。“cons”和诸如“cons onto”的词句，也是函数编程的通用术语。有时运算子有类似作用，特别是在列表处理的情况下，被读作“CONS”。（例如 ML，Scala，F＃和 Elm 编程的 ::运算符，或 Haskell 编程的 :运算符，都是向列表的开头添加一个元素。）

使用

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

有序对

例如 LISP 表达式(cons 1 2)产生一个有序的单元，在左半部存放 1，而右半部存放 2 。

左右次序不能互换（(1 2)跟(2 1)不同）。在 LISP 表示法中，(cons 1 2)结果会印出如下：

(1 . 2)

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

列表

Thumb — 列表(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 的列表为例。

这样的列表经由三个步骤产生：

CONS 3 到nil空列表之上
CONS 2 到上一步的结果之上
CONS 1 到上一步的结果，产生最后的结果

这相当于单一表达式：

(cons 1 (cons 2 (cons 3 nil)))

或可用list函数节略如下：

(list 1 2 3)

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

换言之：

 *--*--*--nil
 |  |  |
 1  2  3

通常结果会被打印为：(1 2 3)

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

树

cons也容易建构出在叶片中储存数据的二叉树。例如以下代码： (cons (cons 1 2) (cons 3 4)) 产生了一棵树：

((1 . 2) . (3 . 4))

即

   *
  / \
 *   *
/ \ / \
1 2 3 4

技术上，前例中的列表（1 2 3）恰巧是不平衡的二叉树。要看到这点，只需重新排列图：

 *--*--*--nil
 |  |  |
 1  2  3

相当于以下：

   *
  / \
 1   *
    / \
   2   *
      / \
     3  nil

函数式实作

由于函数式编程语言如 Haskell, LISP, Scheme都具备了一阶函数，所以 $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”。邱奇编码是一种在无型别的单纯λ演算中，定义数据结构的常用方法，而λ演算则是可计算性质的理论抽象模型，与 Haskell, LISP, Scheme等函数式编程语言密切相关。

这种实作虽然在学术上是有趣的，但不切实际，因为它使得单元与任何其他方案过程不可区分，以及引入不必要的计算低效。然而，相同种类的编码可以用于具有变体的更复杂的代数数据类型，其中它甚至可能变得比其他类型的编码更有效。这种编码还具有可以在不具有变体的静态类型语言（例如 Java）中实现的优点，使用接口而不是 lambdas。

邱奇配对

邱奇配对是以邱奇编码的配对（二元组）类型，表示作用在两个参数之上的函数。当给予参数时，它会将函数应用于该配对的两个组件。 lambda演算中的定义是，

{\begin{aligned}\operatorname {pair} &\equiv \lambda x.\lambda y.\lambda f.f\ x\ y\\\operatorname {first} &\equiv \lambda p.p\ (\lambda x.\lambda y.x)\\\operatorname {second} &\equiv \lambda p.p\ (\lambda x.\lambda y.y)\end{aligned}}

例如,

{\begin{aligned}&\operatorname {first} \ (\operatorname {pair} \ a\ b)\\=&(\lambda p.p\ (\lambda x.\lambda y.x))\ ((\lambda x.\lambda y.\lambda f.f\ x\ y)\ a\ b)\\=&(\lambda p.p\ (\lambda x.\lambda y.x))\ (\lambda f.f\ a\ b)\\=&(\lambda f.f\ a\ b)\ (\lambda x.\lambda y.x)\\=&(\lambda x.\lambda y.x)\ a\ b=a\end{aligned}}

参见

LISP 编程语言
（英文）CAR and CDR（英语：CAR and CDR）
构造器
（英文）代数数据类型（英语：Algebraic data type）
（英文）Hash consing（英语：Hash consing）

参考资料

外部链接