列表構造函式

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

cons構成了存放兩個變數與其指針的記憶體物件，這個物件被稱為（cons）單元、非原子的 S 表達式或（cons 對）。LISP 編程中表達要把 x 加入 y 的語法：(cons x y)，構造了一個新物件。產生的結果具備了左半部，稱為car（第一元素或暫存器位址的內容）；以及右半部稱為cdr（其餘元素或遞減暫存器的內容）。

基本介紹

• 中文名：列表構造函式
• 外文名：list constructor
• 套用領域：數學

使用

雖然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. CONS3 到nil空列表之上
2. CONS2 到上一步的結果之上
3. 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。