列表構造函數

列表構造函數是用來構造列表的基本函數，在大多數 LISP 體系的計算機編程語言中，使用的函數名稱是cons。

cons構成了存放兩個變量與其指針的記憶體物件，這個物件被稱為${\displaystyle CONS}$單元、非原子的 S 表達式或${\displaystyle 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對），並不是普通的“列表”。

列表

 

列表(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則是包含其餘元素的一個子列表。

這形成了簡單基本的列表，而cons，car和cdr函數可以操作列表的內容。

注意，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都具備了一階函數，所以${\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演算中的定義是，

${\displaystyle {\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}}}$ 

例如,

${\displaystyle {\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）

參考資料

外部連結