list - 为什么 Haskell 列表的 `++` 是递归实现的并且花费 O(n) 时间？

Question

据我了解，Haskell 中的列表类似于 C 语言中的链接列表。

所以对于下面的表达式:

a = [1,2,3]
b = [4,5,6]
a ++ b

Haskell 以递归方式实现这一点，如下所示:

(++) (x:xs) ys = x:xs ++ ys

时间复杂度为 O(n) ..

但是，我想知道为什么我不能实现 ++更有效率。

最有效的方法可能是这样的:

复制(fork)a ，我们称之为a' ，在 O(1) 中可能有一些技巧可以做到这一点时间

制作 a' 的最后一个元素指向 b 的第一个元素.这可以在 O(1) 中轻松完成时间..

有人对此有想法吗？谢谢!

Answer 1

这几乎就是递归解决方案所做的。是a的复制品这需要 O(n) (其中 n 是 a 的长度。b 的长度不会影响复杂性)。

复制 n 的列表确实没有“技巧”。 O(1) 时间内的元素。