为什么 `++` for Haskell List 递归实现并且花费 O(n) 时间？
Why is `++` for Haskell List implemented recursively and costs O(n) time?
据我了解，Haskell中的List类似于C语言中的Linked-List。
所以对于下面的表达式：
a = [1,2,3]
b = [4,5,6]
a ++ b
Haskell 以这样的递归方式实现：
(++) (x:xs) ys = x:xs ++ ys
时间复杂度为O(n)..
但是，我想知道为什么我不能更有效地实施 ++。
最高效的方法可能是这样的：
复制（fork）a，我们称它为a'，在O(1)时间[=21]可能会有一些技巧=]
使a'的最后一个元素指向b的第一个元素。这可以在 O(1) 时间内轻松完成..
有人对此有想法吗？谢谢！
这几乎就是递归解决方案所做的。这是 a 的复制，需要 O(n)（其中 n 是 a 的长度。b 的长度不影响复杂性）。
确实没有"trick"在O(1)时间内复制n个元素的列表。
请参阅 copy(fork) 部分是问题 - 递归解决方案正是这样做的（你真的必须这样做，因为你必须调整所有指针a 列表中的元素。
假设 a = [a1,a2,a3] 和 b 是一些列表。
您必须制作 a3 的新副本（我们称之为 a3'），因为它现在不应再指向空列表，而是指向 b 的开头。
然后你必须复制倒数第二个元素 a2 因为它必须指向 a3' 最后 - 出于同样的原因 - 你必须创建一个新的副本a1 也是（指向 a2'）。
这正是递归定义所做的 - 算法没有问题 - 数据结构有问题（连接不好）。
如果您不允许可变性并想要列表的结构，那么您真的无能为力。
你在其他语言中有这个。如果它们提供不可变数据——例如在 .net 中字符串是不可变的——那么字符串连接也存在与这里几乎相同的问题（如果你连接很多字符串，你的程序将执行不佳）。有一些解决方法 (StringBuilder) 可以更好地处理内存占用问题 - 但当然这些不再是不可变的数据结构。
没有办法在常数时间内进行连接，只是因为数据结构的不变性不允许这样做。
您可能认为您可以执行类似于 "cons" 运算符 (:) 的操作，将附加元素 x0 添加到 front 列表 oldList=[x1,x2,x3]（结果为 newList=(x0:oldLIst)），而不必 运行 遍历整个列表。但这只是因为您没有触及现有列表 oldList，而只是引用它。
x0 : ( x1 : ( x2 : ( x3 : [] ) ) )
^ ^
newList oldList
但在您的情况下 (a ++ b)，我们讨论的是更新数据结构深处的引用。您想要用新的尾巴 b 替换 1:(2:(3:[])) 中的 []（[1,2,3] 的显式形式）。只需数一下括号，您就会发现我们必须深入内部才能到达 []。这总是很昂贵，因为我们必须复制整个外部，以确保 a 保持不变。在结果列表中，旧 a 指向哪里才能获得未修改的列表？
1 : ( 2 : ( 3 : b ) )
^ ^
a++b b
这在同一个数据结构中是不可能的。所以我们需要第二个：
1 : ( 2 : ( 3 : [] ) )
^
a
这意味着复制那些 : 节点，这必然会花费第一个列表中提到的线性时间。因此，您提到的 "copy(fork)" 与您所说的不同， 而不是 in O(1).
make a copy(fork) of a, let's call it a', there may be some tricks to do this in O(1) time
当你谈论 "trick" 在恒定时间内分叉某些东西时，你可能会考虑实际上不是制作完整副本，而是创建对原始 a 的引用，并存储更改作为 "annotations"（如提示："modification to tail: use b instead of []"）。
但这就是 Haskell，由于它的懒惰，无论如何！它不会立即执行 O(n) 算法，而只是 "remembers" 您想要一个串联列表，直到您实际访问它的元素。但这并不能使您免于最终支付费用。因为即使一开始引用很便宜（在 O(1) 中，就像你想要的那样），当你访问实际的列表元素时，++ 运算符的每个实例都会增加一点开销（成本"interpreting the annotation" 你添加到你的参考）到连接第一部分中每个元素的访问，最终有效地增加了 O(n) 成本。
据我了解，Haskell中的List类似于C语言中的Linked-List。
所以对于下面的表达式：
a = [1,2,3]
b = [4,5,6]
a ++ b
Haskell 以这样的递归方式实现：
(++) (x:xs) ys = x:xs ++ ys
时间复杂度为O(n)..
但是，我想知道为什么我不能更有效地实施 ++。
最高效的方法可能是这样的：
复制（fork）
a，我们称它为a'，在O(1)时间[=21]可能会有一些技巧=]使
a'的最后一个元素指向b的第一个元素。这可以在O(1)时间内轻松完成..
有人对此有想法吗？谢谢！
这几乎就是递归解决方案所做的。这是 a 的复制，需要 O(n)（其中 n 是 a 的长度。b 的长度不影响复杂性）。
确实没有"trick"在O(1)时间内复制n个元素的列表。
请参阅 copy(fork) 部分是问题 - 递归解决方案正是这样做的（你真的必须这样做，因为你必须调整所有指针a 列表中的元素。
假设 a = [a1,a2,a3] 和 b 是一些列表。
您必须制作 a3 的新副本（我们称之为 a3'），因为它现在不应再指向空列表，而是指向 b 的开头。
然后你必须复制倒数第二个元素 a2 因为它必须指向 a3' 最后 - 出于同样的原因 - 你必须创建一个新的副本a1 也是（指向 a2'）。
这正是递归定义所做的 - 算法没有问题 - 数据结构有问题（连接不好）。
如果您不允许可变性并想要列表的结构，那么您真的无能为力。
你在其他语言中有这个。如果它们提供不可变数据——例如在 .net 中字符串是不可变的——那么字符串连接也存在与这里几乎相同的问题（如果你连接很多字符串，你的程序将执行不佳）。有一些解决方法 (StringBuilder) 可以更好地处理内存占用问题 - 但当然这些不再是不可变的数据结构。
没有办法在常数时间内进行连接，只是因为数据结构的不变性不允许这样做。
您可能认为您可以执行类似于 "cons" 运算符 (:) 的操作，将附加元素 x0 添加到 front 列表 oldList=[x1,x2,x3]（结果为 newList=(x0:oldLIst)），而不必 运行 遍历整个列表。但这只是因为您没有触及现有列表 oldList，而只是引用它。
x0 : ( x1 : ( x2 : ( x3 : [] ) ) )
^ ^
newList oldList
但在您的情况下 (a ++ b)，我们讨论的是更新数据结构深处的引用。您想要用新的尾巴 b 替换 1:(2:(3:[])) 中的 []（[1,2,3] 的显式形式）。只需数一下括号，您就会发现我们必须深入内部才能到达 []。这总是很昂贵，因为我们必须复制整个外部，以确保 a 保持不变。在结果列表中，旧 a 指向哪里才能获得未修改的列表？
1 : ( 2 : ( 3 : b ) )
^ ^
a++b b
这在同一个数据结构中是不可能的。所以我们需要第二个：
1 : ( 2 : ( 3 : [] ) )
^
a
这意味着复制那些 : 节点，这必然会花费第一个列表中提到的线性时间。因此，您提到的 "copy(fork)" 与您所说的不同， 而不是 in O(1).
make a copy(fork) of a, let's call it a', there may be some tricks to do this in O(1) time
当你谈论 "trick" 在恒定时间内分叉某些东西时，你可能会考虑实际上不是制作完整副本，而是创建对原始 a 的引用，并存储更改作为 "annotations"（如提示："modification to tail: use b instead of []"）。
但这就是 Haskell，由于它的懒惰，无论如何！它不会立即执行 O(n) 算法，而只是 "remembers" 您想要一个串联列表，直到您实际访问它的元素。但这并不能使您免于最终支付费用。因为即使一开始引用很便宜（在 O(1) 中，就像你想要的那样），当你访问实际的列表元素时，++ 运算符的每个实例都会增加一点开销（成本"interpreting the annotation" 你添加到你的参考）到连接第一部分中每个元素的访问，最终有效地增加了 O(n) 成本。