Haskell 中的列表操作性能

Question

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

如果我将一个元素添加到 Haskell 中的列表，Haskell returns 一个（完全？）新列表，并且不操作原始列表。

现在假设我有一百万个元素的列表，我在末尾追加了一个元素。 Haskell "copy" 整个列表（100 万个元素）并将元素添加到该副本吗？或者在幕后是否有巧妙的 "trick" 操作以避免复制整个列表？

如果没有 "trick"，复制大型列表的过程是否没有我想象的那么昂贵？

Answer 1

这取决于您使用的数据结构。如果您使用的是普通 Haskell 列表，这些列表类似于 C 或 C++ 中的典型链表实现。使用这种结构，附加和索引（最坏情况）是 O(n) 复杂度，而前置是 O(1) 复杂度。如果您频繁追加并且您的列表呈线性增长，这实际上是 O(n^2)。对于大型列表，这是一个问题。这与您使用的语言无关，Haskell、C、C++、Python、Java、C#，甚至是汇编程序。

但是，如果您要使用像 Data.Sequence.Seq 这样的结构，那么它会在内部使用适当的结构来提供 O(1) 前置和附加，但代价是它可能会占用更多空间内存。不过，所有数据结构都有权衡取舍，具体取决于您要使用哪一个。

或者，您也可以使用 Data.Vector.Vector 或 Data.Array.Array，它们都提供固定长度、连续的内存数组，但是追加和前置非常昂贵，因为您必须将整个数组复制到一个RAM 中的新位置。不过，索引是 O(1)，并且映射或折叠这些结构之一会更快，因为数组的块可以一次放入 CPU 缓存，而不是链表或序列具有元素散布在您的 RAM 中。

Does Haskell "copy" the whole list (1 million elements) and adds the element to that copy?

不一定，编译器可以确定将最后一个值的 next 指针更改为指向新值而不是空列表是否安全，或者如果不安全，则可能需要复制整个列表。不过，这些问题是数据结构固有的，而不是语言固有的。总的来说，我会说 Haskell 的列表比 C 链表更好，因为编译器比程序员更有能力分析何时这是安全的，而 C 编译器不会做这种分析，他们只是照他们说的做。

Answer 2

使用列表时，追加成本很高，必须复制列表，但元素除外。此外，由于新值仅指向原始列表，因此前置很便宜。

将 "third" 附加到 ["first", "second"]：新列表是 (:) "first" ((:) "second" ((:) "third" []))。因此，第一个构造函数必须是一个新的，因为第二个参数必须是一个新值，因为......虽然字符串没有重复。新列表指向内存中的相同字符串。

请注意，在旧值被丢弃的情况下，编译器可能会决定重用它，而不是为新值分配内存并垃圾收集旧值。无论如何，附加将在 O(n) 中完成，因为它需要找到它的结尾。

现在，如果您的程序要向列表追加很多内容，您可能希望使用不同的数据结构以便能够在 O(1) 中追加，例如 DList 形成包 dlist . (https://hackage.haskell.org/package/dlist-0.5/docs/Data-DList.html)

Answer 3

这是一个非常复杂的问题，因为 Haskell 和 GHC 的两个特点：

惰性评价
列表融合

列表融合意味着在某些情况下，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?

有一些技巧可以避免复制整个列表，但是通过附加到它的末尾就可以击败它们。需要理解的是，函数式数据结构通常被设计为 "modify" 它们将利用 结构共享 的操作来尽可能多地重用旧结构。因此，例如，附加两个列表可以这样定义：

(++) :: [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]。经验法则是这样的：

在列表的开头添加元素是最有效的。
在列表末尾添加元素通常效率低下，尤其是当您一遍又一遍地这样做时。

这类问题的一般解决方案是：

修改您的算法，以便您在它们支持的访问模式中有效地使用列表。
不要使用列表；使用其他一些序列数据结构，这些数据结构可以有效地支持您手头问题所需的访问模式。另一个答案提到了差异列表，但其他值得一提的是：

Haskell 中的列表操作性能

List manipulation performance in Haskell

haskell

list

append

immutability

data-structures