关于来自noobie功能程序员的列表访问的问题

Question

这可能是一个愚蠢而明显的问题,但为什么列表访问算法示例是在线性时间内实现的？据我所知,大多数应用程序涉及遍历列表而不是随机访问它们,但是如果要在随机访问的列表上执行访问会怎么样？

Answer 1

因为列表是按设计线性结构的.它们是规范的递归数据类型,定义如下:

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

也就是说,空列表或cons节点,由一个元素和一个尾部组成,它也是一个列表.

这种结构精确地对应于数学中的归纳定义,并且相应地使得将许多函数编写为简单的递归调用变得微不足道.

但是,递归数据类型不允许在非线性时间内随机访问.为此,您需要硬件支持(我们都有),以及更复杂的数据类型(或者不太复杂,具体取决于您的观点).

摘要:列表是计算机科学将归纳编码为递归数据结构.它是基础,你需要它,但它不做随机访问.

Answer 2

Haskell列表对应于命令式语言中的链表; 它们本质上是顺序的,因为您只能访问头部并需要遍历以查找其他元素.

如果要随机访问,则应选择其他一些数据类型.也许来自Data.Array或Data.IntMap.