哈斯克尔的"尾巴"函数有什么时间复杂性？

Question

当我想到自己时,我正在阅读关于Haskell的教程; Haskell的tail功能具有多大的时间复杂性(以及为什么)？(我在任何文档中都找不到答案)

我猜想对于大小为n的列表,tail函数将是O(n),即只是将尾部复制到新列表并返回该列表.但话说回来,我不太了解Haskell的底层架构(我是语言的新手).

当然,我可以计时.但我还不知道如何在Haskell中计算时间,我也想了解Haskell如何处理问题,证明为什么它是O(n)/ O(1)或其他什么.

提前致谢 :)

Answer 1

Haskell语言没有指定.但在GHC(最常用的实现)中,它是O(1).尾部不需要复制 - 在原始列表和只使用列表尾部的人之间共享是安全的 - 因为Haskell中的所有内容都是不可变的.

挑战问题:init除了列表的最后一个元素之外,为什么会在O(n)中运行？为什么上面的共享参数不适用于那里？

至于挑战问题; 如果我可以假设列表是一个单链表(如Williems的答案中所述),它应该是O(n),因为没有一个没有最后一个元素的列表没有删除指针的指针最后一个元素(不可能)或将值复制到不包含最后一个元素的新链接列表.这是正确的推理方式吗？ (4认同)

Answer 2

简短回答:如果列表已构建到该节点,则为O(1).

Haskell中的列表是一个链表.它被定义为:

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

这意味着要么我们有空列表,要么有a : [a]构造.所以一个节点有一个head(a)引用一个类型的对象a,一个tail引用一个列表[a](可以是空列表,或另一个节点).

tailin 的源代码base定义为:

tail                    :: [a] -> [a]
tail (_:xs)             =  xs
tail []                 =  errorEmptyList "tail"

它在O(1)中运行,因为我们只需按指向该节点的"尾部".

但请注意Haskell懒惰地工作.这不是因为我们得到一个类型的对象[a],我们有一个物化列表:通常Haskell首先必须评估它已经放弃给定节点的表达式树.这可能导致评估复杂且耗时的算法.所以它取决于你给出的表达式树.