查看“︁列表構造函數”︁的源代码

{{Multiple issues|
{{Expert|time=2018-11-12}}
{{unreferenced|time=2017-02-27T04:12:26+00:00}}
}}
'''列表構造函數'''是用來構造[[串列_(抽象資料型別)|列表]]的基本[[函數]]，在大多數 [[LISP]] 體系的計算機編程語言中，使用的函數名稱是'''<code>cons</code>'''。

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

以上約略地和物件導向的[[構造器]]概念相關，即產生一個給定參數的新物件，而其與代數數據類型系統的構造函數，有更密切相關。“''cons''”和諸如“''cons onto''”的詞句，也是函數編程的通用術語。有時[[運算子]]有類似作用，特別是在列表處理的情況下，被讀作“CONS”。（例如 ML，Scala，F＃和 Elm 編程的 <code>::</code>運算符，或 Haskell 編程的 <code>:</code>運算符，都是向列表的開頭添加一個元素。）

==使用==
雖然''cons''單元可用於儲存有序的數據對，但它們更常用於組合為更複雜的複合數據結構，特別是[[連結串列|列表]]和[[二元樹]]。

=== 有序對 ===
例如 LISP 表達式<code>(cons 1 2)</code>產生一個有序的單元，在左半部存放 1，而右半部存放 2 。

左右次序不能互換（(1 2)跟(2 1)不同）。在 LISP 表示法中，<code>(cons 1 2)</code>結果會印出如下：

 (1 . 2)

須注意 1 和 2 之間的句點；這個 S 表達式是特殊的“點對”（所謂的''cons對''），並不是普通的“列表”。

===列表===
[[Image:Cons-cells.svg|thumb|left|350px|列表(42 69 613)的 Cons單元圖，以<tt>cons</tt>構造函數寫成：<syntaxhighlight lang="lisp">(cons 42 (cons 69 (cons 613 nil)))</syntaxhighlight>此外可用<tt>list</tt>函數寫成：
<syntaxhighlight lang="lisp">(list 42 69 613)</syntaxhighlight>]]
{{clear}}

LISP 編程中的列表實作在「cons對」之上。具體地說，每個列表的[[結構]]都是：

#一個空列表 <code>()</code>，通常被稱為 <code>nil</code> 的特殊物件。
#一個''cons''單元，<code>car</code>代表這列表的第一個元素，而<code>cdr</code>則是包含其餘元素的一個子列表。

這形成了簡單基本的[[連結串列|列表]]，而<code>cons</code>，<code>car</code>和<code>cdr</code>函數可以操作列表的內容。

注意，<code>nil</code>是個特殊的空列表，並不是「cons對」。考慮元素為 1,2 和 3 的列表為例。

這樣的列表經由三個步驟產生：

#''CONS'' 3 到<code>nil</code>空列表之上
#''CONS'' 2 到上一步的結果之上
#''CONS'' 1 到上一步的結果，產生最後的結果

這相當於單一表達式：
<syntaxhighlight lang="lisp">(cons 1 (cons 2 (cons 3 nil)))</syntaxhighlight>

或可用<code>list</code>函數節略如下：
<syntaxhighlight lang="lisp">(list 1 2 3)</syntaxhighlight>

最終結果是一個列表，形式如右：<code>(1 . (2 . (3 . nil)))</code>

換言之：
  *--*--*--nil
  |  |  |
  1  2  3

通常結果會被打印為：<code>(1 2 3)</code>

因此<code>cons</code>操作會在既有列表的最前頭，添加一個元素。例如，如果''x''是上面定義的列表，那麼<code>(cons 5 x)</code>將產生列表：<code>(5 1 2 3)</code> 。另一個有用的函數是<code>append</code>，用於合併兩個列表。

===樹===
<code>cons</code>也容易建構出在葉片中儲存數據的二元樹。例如以下代碼：
<code>(cons (cons 1 2) (cons 3 4))</code>
產生了一棵樹：

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

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

技術上，前例中的列表（1 2 3）恰巧是不平衡的二元樹。要看到這點，只需重新排列圖：

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

相當於以下：
    *
   / \
  1   *
     / \
    2   *
       / \
      3  nil

==函數式實作==
由於函數式編程語言如 Haskell, LISP, Scheme都具備了一階函數，所以<math>CONS</math>單元或其它種類的數據結構，都可使用函數實現。例如，在 Scheme 中：
<syntaxhighlight lang="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)))
</syntaxhighlight>

這種技術被稱為[[邱奇數|邱奇編碼]]，實作出了<code>cons</code>、<code>car</code> 和 <code>cdr</code>操作，使用函數的特性來當作“cons cell”。邱奇編碼是一種在無型別的單純λ演算中，定義數據結構的常用方法，而λ演算則是可計算性質的理論抽象模型，與 Haskell, LISP, Scheme等函數式編程語言密切相關。

這種實作雖然在學術上是有趣的，但不切實際，因為它使得單元與任何其他方案過程不可區分，以及引入不必要的計算低效。然而，相同種類的編碼可以用於具有變體的更複雜的代數數據類型，其中它甚至可能變得比其他類型的編碼更有效。這種編碼還具有可以在不具有變體的靜態類型語言（例如 [[Java]]）中實現的優點，使用接口而不是 lambdas。


==邱奇配對==
{{see also|邱奇數}}
邱奇配對是以邱奇編碼的配對（二元組）類型，表示作用在兩個參數之上的函數。當給予參數時，它會將函數應用於該配對的兩個組件。 lambda演算中的定義是，

: <math>\begin{align}
\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{align}
</math>

例如,
: <math>\begin{align}
   & \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{align}
</math>

== 參見 ==
* [[LISP|LISP 編程語言]]
* {{en}}{{link-en|CAR and CDR|CAR and CDR}}
* [[構造器]]
* {{en}}[[代數數據類型]]
* {{en}}{{link-en|Hash consing|Hash consing}}

==參考資料==
{{Reflist}}

== 外部連結 ==
{{Translation/Ref|en|Cons}}

{{Computer Science}}

[[Category:LISP程式語言]]
[[Category:函數式編程]]
[[Category:计算机编程]]
[[Category: 数据类型]]