Haskell 中的列表操作性能

Question

我目前正在学习 Haskell，我对以下内容感到好奇:

如果我向 Haskell 中的列表添加一个元素，Haskell 将返回一个(完全？)新列表，并且不会操作原始列表。

现在假设我有一个包含一百万个元素的列表，并且我在末尾添加了一个元素。 Haskell 是否“复制”整个列表(100 万个元素)并将该元素添加到该副本中？或者幕后是否有一个巧妙的“技巧”来避免复制整个列表？

如果没有“技巧”，复制大型列表的过程是否不像我想象的那么昂贵？

Answer 1

这是一个令人惊讶的复杂问题，因为 Haskell 和 GHC 的两个特性:

1. 惰性评估
2. 列表融合

列表融合意味着在某些情况下，GHC 可以将列表处理代码重写为不分配列表单元的循环。因此，根据使用的上下文，相同的代码可能不会产生额外的成本。

惰性求值意味着如果一个操作的结果没有被消耗，那么你就不需要支付计算它的成本。例如，这很便宜，因为您只需构造列表的前十个元素:

example = take 10 ([1..1000000] ++ [1000001])

事实上，在该代码中，take 10 可以与列表追加融合，因此它与 [1..10] 相同。

但是我们假设我们正在使用我们创建的所有列表的所有元素，并且编译器没有融合我们的列表操作。现在回答您的问题:

If I add an element to a List in Haskell, Haskell returns a (completly?) new list, and doesn't manipulate the original one. Now let's say I have a List of a million elements and I append one element at the end. Does Haskell "copy" the whole list (1 million elements) and adds the element to that copy? Or is there a neat "trick" going on behind the scenes to avoid copying the whole list?

存在避免复制整个列表的技巧，但通过 append 到其末尾，您可以击败它们。需要理解的是，函数式数据结构通常被设计为“修改”它们的操作将利用结构共享来尽可能多地重用旧结构。例如， append 两个列表可以这样定义:

(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys

查看此定义，您可以看出列表 ys 将在结果中重用。因此，如果我们有 xs = [1..3]、ys = [4..5] 和 xs++ ys，全部完全立即评估并保留在内存中，从内存角度来看，它看起来像这样:

           +---+---+    +---+---+    +---+---+
      xs = | 1 | -----> | 2 | -----> | 3 | -----> []
           +---+---+    +---+---+    +---+---+

           +---+---+    +---+---+ 
      ys = | 4 | -----> | 5 | -----> []
           +---+---+    +---+---+    
             ^
             |
             +------------------------------------+
                                                  |
           +---+---+    +---+---+    +---+---+    |
xs ++ ys = | 1 | -----> | 2 | -----> | 3 | -------+
           +---+---+    +---+---+    +---+---+

这就是长话短说:如果你执行xs++ ys，并且它没有融合，并且你消耗了整个列表，那么这将创建的副本>xs 但将内存重用于ys。

但是现在让我们再看看你的问题:

Now let's say I have a List of a million elements and I append one element at the end. Does Haskell "copy" the whole list (1 million elements) and adds the element to that copy?

这将类似于 [1..1000000]++ [1000001]，是的，它会复制整整一百万个元素。但另一方面，[0]++ [1..1000000]只会复制[0]。经验法则是这样的:

• 在列表开头添加元素效率最高。
• 在列表末尾添加元素通常效率很低，尤其是一遍又一遍地这样做时。

解决此类问题的一般方法是:

1. 修改您的算法，以便您按照列表有效支持的访问模式使用列表。
2. 不要使用列表；使用其他一些序列数据结构，可以有效地支持当前问题所需的访问模式。另一个答案提到了差异列表，但其他值得一提的是:
   • Data.Sequence
   • Data.Set
   • Data.Vector