菜鸟函数式程序员关于列表访问的问题
这可能是一个愚蠢而明显的问题，但为什么列表访问算法示例是在线性时间内实现的？我知道大多数应用程序都涉及遍历列表而不是随机访问它们，但是如果您想通过随机访问对列表进行访问该怎么办？
This might be a silly and obvious question, but why are list access algorithm examples implemented in linear time? I understand that most applications involve traversing lists rather than accessing them randomly, but what if you want to perform an access on a list with random accesses?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
因为列表被设计为线性结构。它们是规范的递归数据类型，定义为：
也就是说，要么是空列表，要么是 cons 节点，由一个元素和一个尾部（也是一个列表）组成。
这种结构精确地对应于数学中的归纳定义，相应地，使得将许多函数编写为简单的递归调用变得微不足道。
然而，递归数据类型不允许非线性时间内的随机访问。为此，您需要硬件支持（我们都有）和更复杂的数据类型（或不太复杂，取决于您的观点）。
总结：列表是计算机科学对归纳法的编码，是一种递归数据结构。这是基础，你需要它，但它不进行随机访问。
Because lists are by design a linear structure. They are the canonical recursive data type, defined as:
That is, either the empty list, or a cons node, consisting of an element, and a tail, which is also a list.
This structure precisely corresponds to inductive definitions in mathematics, and correspondingly, makes it trivial to write many functions as simple recursive calls.
The recursive data type does not admit random access in non-linear time, however. For that you need hardware support (which we all have), and a more sophisticated data type (or less sophisticated, depending on your viewpoint).
Summary: lists are computer science's encoding of induction as a recursive data structure. It's fundamental, you need it, but it doesn't do random access.
Haskell 列表对应于命令式语言中的链表；它们本质上是顺序的，因为您只能访问头部并且需要遍历以查找其他元素。
如果您想要随机访问，您应该选择其他数据类型。也许来自 Data.Array 或 Data.IntMap。
Haskell lists correspond to linked lists in imperative languages; they are inherently sequential since you only have access to the head and need to traverse to find other elements.
If you want random access you should choose some other data type. Perhaps from Data.Array or Data.IntMap.