列表构造函数

(1 . 2)

(cons 42 (cons 69 (cons 613 nil)))

(list 42 69 613)

LISP 编程中的列表实作在“cons对”之上。具体地说，每个列表的结构都是：

这形成了简单基本的列表，而cons，car和cdr函数可以操作列表的内容。

注意，nil是个特殊的空列表，并不是“cons对”。考虑元素为 1,2 和 3 的列表为例。

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

这相当于单一表达式：

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

或可用list函数节略如下：

(list 1 2 3)

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

换言之：

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

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

因此cons操作会在既有列表的最前头，添加一个元素。例如，如果是上面定义的列表，那么(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都具备了一阶函数，所以${\displaystyle 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演算中的定义是，

例如,