跳转到内容

列表构造函数

维基百科,自由的百科全书

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

cons构成了存放两个变量与其指针的记忆体物件,这个物件被称为单元、非原子的 S 表达式对。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对),并不是普通的“列表”。

列表

[编辑]
列表(42 69 613)的 Cons单元图,以cons构造函数写成:
(cons 42 (cons 69 (cons 613 nil)))
此外可用list函数写成:
(list 42 69 613)

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

  1. 一个空列表 (),通常被称为 nil 的特殊物件。
  2. 一个cons单元,car代表这列表的第一个元素,而cdr则是包含其余元素的一个子列表。

这形成了简单基本的列表,而conscarcdr函数可以操作列表的内容。

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

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

  1. CONS 3 到nil空列表之上
  2. CONS 2 到上一步的结果之上
  3. 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都具备了一阶函数,所以单元或其它种类的数据结构,都可使用函数实现。例如,在 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)))

这种技术被称为邱奇编码,实作出了conscarcdr操作,使用函数的特性来当作“cons cell”。邱奇编码是一种在无型别的单纯λ演算中,定义数据结构的常用方法,而λ演算则是可计算性质的理论抽象模型,与 Haskell, LISP, Scheme等函数式编程语言密切相关。

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


邱奇配对

[编辑]

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

例如,

参见

[编辑]

参考资料

[编辑]

外部链接

[编辑]