Rad*_*scu 6 complexity-theory haskell functional-programming algebraic-data-types
根据ADT的理论(代数数据类型)两个表中的级联必须考虑O(n)那里n是第一个列表的长度.基本上,您必须递归遍历第一个列表,直到找到结束.
从不同的角度来看,可以说第二个列表可以简单地链接到第一个元素的最后一个元素.如果知道第一个列表的结尾,这将花费恒定的时间.
我在这里错过了什么？
在操作上,Haskell列表通常由指向单链表的第一个单元的指针(粗略地)表示.这样,tail只返回指向下一个单元格的指针(它不必复制任何东西),并x :在列表前面进行分配一个新单元格,使其指向旧列表,并返回新指针.旧指针访问的列表未更改,因此无需复制它.
如果你改为附加一个值++ [x],那么你不能通过改变它的最后一个指针来修改原始的喜欢列表,除非你知道永远不会访问原始列表.更具体地说,考虑一下
x = [1..5]
n = length (x ++ [6]) + length x
如果你x在做什么时修改x++[6],那么值n将变为12,这是错误的.最后一个x引用具有长度的未更改列表5,因此结果n必须为11.
实际上,您不能指望编译器对此进行优化,即使在x不再使用的情况下,理论上也可以在适当的位置更新("线性"使用).所发生的事情是,x++[6]必须为最坏情况做好准备,x之后再重复使用,因此必须复制整个列表x.
正如@Ben所说,"列表被复制"是不精确的.实际发生的是具有指针的单元格被复制(列表中所谓的"脊柱"),但元素不是.例如,
x = [[1,2],[2,3]]
y = x ++ [[3,4]]
只需要分配[1,2],[2,3],[3,4] 一次.列表列表x,y将共享指向整数列表的指针,这些指针不必重复.
这是因为不可变状态。列表是一个对象+一个指针，所以如果我们将列表想象为元组，它可能看起来像这样：
let tupleList = ("a", ("b", ("c", [])))
现在让我们使用“head”函数获取此“列表”中的第一项。这个 head 函数需要 O(1) 时间，因为我们可以使用 fst：
> fst tupleList
如果我们想用另一个项目替换列表中的第一项，我们可以这样做：
let tupleList2 = ("x",snd tupleList)
这也可以在 O(1) 内完成。为什么？因为列表中绝对没有其他元素存储对第一个条目的引用。由于状态不可变，我们现在有两个列表，tupleList和tupleList2。当我们制作时，tupleList2我们没有复制整个列表。因为原始指针是不可变的，所以我们可以继续引用它们，但在列表的开头使用其他内容。
现在让我们尝试获取 3 项列表的最后一个元素：
> snd . snd $ fst tupleList
这发生在 O(3) 中，它等于我们列表的长度，即 O(n)。
但是我们不能存储一个指向列表中最后一个元素的指针并以 O(1) 的时间访问它吗？为此，我们需要一个数组，而不是列表。数组允许任何元素的查找时间为 O(1)，因为它是在寄存器级别实现的原始数据结构。
（旁白：如果您不确定为什么我们要使用链表而不是数组，那么您应该更多地阅读有关数据结构、数据结构算法以及各种操作（如 get、poll、insert）的 Big-O 时间复杂度的内容、删除、排序等）。
现在我们已经确定了这一点，让我们看看串联。让我们连接tupleList一个新列表，("e", ("f", []))。为此，我们必须遍历整个列表，就像获取最后一个元素一样：
tupleList3 = (fst tupleList, (snd $ fst tupleList, (snd . snd $ fst tupleList, ("e", ("f", [])))
上面的操作实际上比 O(n) 时间更糟糕，因为对于列表中的每个元素，我们必须重新读取列表直到该索引。但是，如果我们暂时忽略这一点并关注关键方面：为了到达列表中的最后一个元素，我们必须遍历整个结构。
您可能会问，为什么我们不将最后一个列表项存储在内存中呢？这样，追加到列表末尾的时间复杂度为 O(1)。但不能这么快，我们无法在不更改整个列表的情况下更改最后一个列表项。为什么？
让我们看一下它的样子：
data Queue a = Queue { last :: Queue a, head :: a, next :: Queue a} | Empty
appendEnd :: a -> Queue a -> Queue a
appendEnd a2 (Queue l, h, n) = ????
如果我修改“last”（这是一个不可变变量），我实际上不会修改队列中最后一项的指针。我将创建最后一个项目的副本。引用该原始项目的其他所有内容都将继续引用原始项目。
因此，为了更新队列中的最后一项，我必须更新引用它的所有内容。这只能在最佳 O(n) 时间内完成。
因此，在我们的传统列表中，我们有最后一项：
List a []
但如果我们想改变它，我们会复制它。现在倒数第二项引用了旧版本。所以我们需要更新该项目。
List a (List a [])
但如果我们更新倒数第二个项目，我们就会复制它。现在倒数第三个项目有一个旧的参考。所以我们需要更新它。重复直到到达列表的头部。我们回到了原点。没有任何东西保留对列表头部的引用，因此编辑需要 O(1)。
这就是 Haskell 没有双向链表的原因。这也是为什么“队列”（或至少是 FIFO 队列）不能以传统方式实现的原因。在 Haskell 中创建队列涉及对传统数据结构的一些认真的重新思考。
如果您对这一切是如何工作的更加好奇，请考虑阅读《纯功能数据结构》一书。
编辑：如果您曾经见过这个： http: //visualgo.net/list.html，您可能会注意到在可视化中“插入尾部”发生在 O(1) 中。但为了做到这一点，我们需要修改列表中的最后一个条目以给它一个新的指针。更新指针会改变状态，这在纯函数式语言中是不允许的。希望我的帖子的其余部分能够清楚地说明这一点。