Loading AI tools
来自维基百科,自由的百科全书
列表構造函數是用來構造列表的基本函數,在大多數 LISP 體系的計算機編程語言中,使用的函數名稱是cons
。
![]() |
cons
構成了存放兩個變量與其指針的記憶體物件,這個物件被稱為單元、非原子的 S 表達式或對。LISP 編程中表達要把 x 加入 y 的語法:(cons x y)
,構造了一個新物件。產生的結果具備了左半部,稱為CAR
(第一元素或暫存器位址的內容);以及右半部稱為CDR
(其餘元素或遞減暫存器的內容)。
以上約略地和物件導向的構造器概念相關,即產生一個給定參數的新物件,而其與代數數據類型系統的構造函數,有更密切相關。「cons」和諸如「cons onto」的詞句,也是函數編程的通用術語。有時運算子有類似作用,特別是在列表處理的情況下,被讀作「CONS」。(例如 ML,Scala,F#和 Elm 編程的 ::
運算符,或 Haskell 編程的 :
運算符,都是向列表的開頭添加一個元素。)
例如 LISP 表達式(cons 1 2)
產生一個有序的單元,在左半部存放 1,而右半部存放 2 。
左右次序不能互換((1 2)跟(2 1)不同)。在 LISP 表示法中,(cons 1 2)
結果會印出如下:
(1 . 2)
須注意 1 和 2 之間的句點;這個 S 表達式是特殊的「點對」(所謂的cons對),並不是普通的「列表」。
(cons 42 (cons 69 (cons 613 nil)))
(list 42 69 613)
LISP 編程中的列表實作在「cons對」之上。具體地說,每個列表的結構都是:
()
,通常被稱為 nil
的特殊物件。car
代表這列表的第一個元素,而cdr
則是包含其餘元素的一個子列表。這形成了簡單基本的列表,而cons
,car
和cdr
函數可以操作列表的內容。
注意,nil
是個特殊的空列表,並不是「cons對」。考慮元素為 1,2 和 3 的列表為例。
這樣的列表經由三個步驟產生:
nil
空列表之上這相當於單一表達式:
(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)))
這種技術被稱為邱奇編碼,實作出了cons
、car
和 cdr
操作,使用函數的特性來當作「cons cell」。邱奇編碼是一種在無型別的單純λ演算中,定義數據結構的常用方法,而λ演算則是可計算性質的理論抽象模型,與 Haskell, LISP, Scheme等函數式編程語言密切相關。
這種實作雖然在學術上是有趣的,但不切實際,因為它使得單元與任何其他方案過程不可區分,以及引入不必要的計算低效。然而,相同種類的編碼可以用於具有變體的更複雜的代數數據類型,其中它甚至可能變得比其他類型的編碼更有效。這種編碼還具有可以在不具有變體的靜態類型語言(例如 Java)中實現的優點,使用接口而不是 lambdas。
邱奇配對是以邱奇編碼的配對(二元組)類型,表示作用在兩個參數之上的函數。當給予參數時,它會將函數應用於該配對的兩個組件。 lambda演算中的定義是,
例如,
![]() |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.