haskell - 为什么列表的连接需要 O(n)？

Question

根据 ADT(代数数据类型)理论，两个列表的连接必须采用 O(n)在哪里 n是第一个列表的长度。基本上，您必须递归地遍历第一个列表，直到找到结尾。

从不同的角度来看，可以说第二个列表可以简单地链接到第一个列表的最后一个元素。如果知道第一个列表的结尾，这将花费恒定的时间。

我在这里想念什么？

Answer 1

在操作上，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将共享指向整数列表的指针，这些指针不必重复。