Haskell ~ last函数是否遍历整个列表？

Question

简单的问题，问Haskellites：Haskell是否迭代整个序列以获取最后一个值？具体来说，这两个表达式执行的指令数量是否不同？

Prelude> last "asdf"
'f'
Prelude> last "qwerty"
'y'

- Squirrelsama

---

顺便提一下，如果你经常需要调用“last”，那么存在其他数据结构可以使用（而不是列表/字符串），在这些数据结构中，该操作比遍历整个列表更快。 - ShreevatsaR

特别是在ShreevatsaR的指导下，位于Haskell语言containers库中的Data.Sequence提供了一种“指示树”数据结构，可以以O(1)的时间复杂度访问序列的最后一个元素。 - Don Stewart

你可以通过查看定义来自行了解。要查找定义，请在Hoogle中搜索"last"，并单击文档中的"source"链接。 - Thomas M. DuBuisson

Answer 1

是的，Haskell的列表是单链表，因此last需要遍历整个列表，使其运行时间为O(n)。

- sepp2k

---

@sepp2k：考虑到这个答案的显然正确，我最好的猜测是有人用iPhone上的手指不小心点了赞。 - Chuck

因为gdi的回答鼓励进行实验来确定答案，而不仅仅是直接说出答案。 - luqui

@luqui：鼓励他阅读源代码，我可能会理解，但“进行实验”并不是确定函数运行时间的好方法，我认为这不应该被鼓励。这基本上是在鼓励人们在不理解的情况下接受事物。首先，尝试一些东西并发现对于更大的参数需要更长的时间，几乎不能证明一个函数需要O(n)的时间。其次，尝试并发现它需要更长的时间，并不能解释为什么它需要更长的时间（这就是说Haskell列表是单向链接的原因）。 - sepp2k

@sepp2k，我把SO视为一个教育网站——毕竟，人们来这里是为了学习（非常具体的）东西。我通常支持与我对待学生的方式相一致的答案。我会鼓励学生进行实验，而不是告诉他答案。我承认，将SO提问者视为学生的假设并不普遍（只是给他们该死的信息），对于那些不同意的人来说，幸运的是我只有一票来表达我的价值观。 - luqui

我可以理解如果你说“阅读源代码”，但是任何教授（或助教或其他教育工作者）在被问到“这个函数的运行时间复杂度是什么？”时回答“尝试一下，看看需要多长时间”是不太好的表现，依我看。 - sepp2k

Answer 2

除了sepp2k所说的之外，这很容易确定：只需运行“last [1..1000000000]”并查看是否需要一段时间。如预期的那样，它确实需要一段时间。

- gdj

Answer 3

正如其他两个答案所说：是的，对于标准列表，last是O(n)的操作。如果您正在处理文本数据，可以考虑使用text package，该软件包提供了一个O(1)的last function。如果您不处理文本数据，则可以查看bytestring或vector软件包。

- Michael Snoyman