Haskell 的 `!?` 运算符的摊余时间复杂度是多少？

Question

文档说：

列表索引（下标）运算符，从0开始。如果索引越界，则返回Nothing 这是部分的完全变体！操作员。 警告：此函数在索引中需要线性时间。

然而时间表明并非如此，也许是因为 GHC 每次评估外部上下文时只计算一次表达式？

ghci> length $ map ([0..10^8-1] !?) . map (`mod` (10^8 - 1)) $ [0..1 * 10^8 - 1]
100000000
(1.16 secs, 24,800,308,224 bytes)
ghci> length $ map ([0..10^8-1] !?) . map (`mod` (10^8 - 1)) $ [0..4 * 10^8 - 1]
400000000
(4.55 secs, 99,200,308,200 bytes)

有谁知道有权威的参考资料来解决这个问题吗？

Answer 1

然而，时间却表明并非如此。

它根本不计算

!?

：您要求列表的长度，因此它不需要确定列表本身中的项目。事实上，

length

本质上被确定为：

length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs

它不必评估列表中的项目。如果你有类似的东西：

length [undefined, undefined]

它仍然会返回

2

，并且：

length [slow_function, slow_function]

它甚至永远不会触发

slow_function

。

Haskell 中的列表的实现类似于

Lisp 列表 [wiki]，它们与 Java 等中的链表非常相似，只不过它们是不可变的。因此，它需要遍历 n 节点才能到达第 n 个节点，从而实现线性缩放。由于缓存，第二次浏览同一个列表确实可能比第一次快（一点），但仍然需要 n 跳，但这通常会花费机器更少的时间来完成一跳。 因此，

列表

不适合随机访问 [wiki]操作：通常列表用于对其进行枚举。如果您需要随机访问，通常使用 Array

 [Hackage]，或其他一些数据结构。