Haskell~最后迭代整个列表吗？

Question

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

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

Answer 1

是的,Haskell的列表是单独链接的,因此last需要遍历整个列表,从而实现其运行时O(n).

@luqui:正如我所说的,如果你说"阅读来源",我会理解它,但任何教授(或TA或其他教育工作者)在被问到"什么是跑步"时回答"试试看看需要多长时间"这个功能的时间复杂性？" 是不是做得很好恕我直言. (3认同)
@ sepp2k:考虑到这个答案是多么明确的正确,我最好的猜测是iPhone上的某个人发了一个胖子. (2认同)

Answer 2

除了sepp2k所说的,这很容易确定:只需运行"last [1..1000000000]"并查看是否需要一段时间.正如预期的那样.