這是使用cons的列表的定義嗎？

Question

在本文中，我看到一個定義列表（T是你想要的任何類型）：

listof T ::= Nil | Cons T (listof T) 

我覺得這個說：

T類型的列表被定義爲Nil或結果函數cons應用於類型爲T的列表，其中cons將該列表與另一個列表（餘下的 - 可能是nil）鏈接。

這是一個準確的描述嗎？

Answer 1

是的。這就是Lisp lists的構建方式。

這是鏈接列表。由於Nil或Cons是內存中的對象，因此我們爲列表中的每個元素都有一個對象。該對象 - 給定它是一個Cons - 兩個引用：一個指向該列表在該位置保存的元素，另一個指向鏈接列表中的下一個節點。

所以，如果你存儲一個列表(1,4,2,5)，然後在內部，它被存儲爲：

+---+---+ +---+---+ +---+---+ +---+---+ 
| o | o---->| o | o---->| o | o---->| o | o----> Nil 
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ 
    v   v   v   v 
    1   4   2   5 

或者你可以構建像Cons 1 (Cons 4 (Cons 2 (cons 4 Nil)))。

Lisp列表的概念在功能和邏輯編程語言中相當流行。

使用鏈接列表通常需要編寫與使用數組和列表列表不同的算法。獲得第012個元素將需要O（k）時間，所以通常要防止這種情況。因此，人們通常遍歷列表並且例如發出某些元素（例如，這些元素滿足給定的謂詞）。