为什么Haskell List的`++`递归实现并花费O(n)时间？

Question

据我所知,Haskell中的List类似于C语言中的Linked-List.

所以对于以下表达式:

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

Haskell以递归的方式实现这个:

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

时间的复杂性是O(n)......

但是,我想知道为什么我不能++更有效地实施.

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

1. 复制(分叉)a,让我们称之为a',可能有一些技巧可以O(1)及时完成

2. 使最后一个元素a'指向第一个元素b.这可以很容易地O(1)及时完成..

有没有人有这个想法？谢谢!

Answer 1

这几乎就是递归解决方案的作用.它的复制a需要O(n)(其中n长度为a.长度b不影响复杂性).

n在O(1)时间内复制元素列表实际上没有"技巧" .

Answer 2

看到副本(fork)部分是问题 - 递归解决方案正是这样做的(你真的必须这样做,因为你必须调整a列表中元素的所有指针.

让我们说a = [a1,a2,a3]并且b是一些清单.

你必须制作一个新的副本a3(让我们称之为a3'),因为它现在应该不再指向一个空列表,而是指向它的开头b.

然后你必须复制倒数第二个元素,a2因为它必须指向a3'并最终 - 出于同样的原因 - 你必须创建一个新的副本a1(指向a2').

这正是递归定义所做的 - 它对算法没有问题 - 它是数据结构的问题(它对串联来说不太好).

如果你不允许可变性并且想要列表的结构,你真的可以做其他事情.

你有其他langs.如果它们提供不可变数据 - 例如.net字符串是不可变的 - 所以字符串连接几乎与此处相同(如果你连接很多字符串,你的程序将表现不佳).有一种解决方法(StringBuilder)可以更好地处理内存占用 - 但当然这些不再是不可变的数据结构.