这是使用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）时间，所以通常要防止这种情况。因此，人们通常遍历列表并且例如发出某些元素（例如，这些元素满足给定的谓词）。