data-structures - 一个菜鸟函数式程序员关于列表访问的问题

Question

这可能是一个愚蠢而明显的问题，但为什么列表访问算法示例在线性时间内实现？我知道大多数应用程序涉及遍历列表而不是随机访问它们，但是如果您想对具有随机访问的列表执行访问怎么办？

Answer 1

因为列表是设计成线性结构的。它们是规范的递归数据类型，定义为:

 data [a] = [] | a : [a]

也就是说，要么是空列表，要么是由一个元素和一个尾部(也是一个列表)组成的 cons 节点。

这种结构恰好对应于数学中的归纳定义，相应地，将许多函数编写为简单的递归调用变得微不足道。

然而，递归数据类型不允许在非线性时间内进行随机访问。为此，您需要硬件支持(我们都有)和更复杂的数据类型(或不太复杂，取决于您的观点)。

摘要:列表是计算机科学将归纳编码为递归数据结构的方法。这是基本的，您需​​要它，但它不会进行随机访问。