这是使用 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 列表的概念在 函数式 和逻辑编程语言中都很流行。

使用链表通常需要编写与使用数组和数组列表不同的算法。获得第 k 个元素将需要 O(k) 时间，因此通常旨在防止这种情况发生。因此，通常会遍历列表，例如发出某些元素（假设这些元素满足给定的谓词）。

这是使用 cons 的列表的定义吗？

Is this the definition for a list using cons?

functional-programming

list

cons