Haskell:列表，数组，向量，序列

我正在学习Haskell，并阅读了几篇关于Haskell列表和(插入您的语言)数组的性能差异的文章。

作为一个学习者，我显然只是使用列表，甚至没有考虑性能差异。 我最近开始调查，发现Haskell中有许多可用的数据结构库

有没有人能解释一下列表、数组、向量、序列之间的区别，而不是深入研究数据结构的计算机科学理论?

此外，是否存在使用一种数据结构而不是另一种数据结构的通用模式?

是否还有其他形式的数据结构是我遗漏的，但可能有用?

40567 次浏览
小开
最佳答案

列出了岩石

到目前为止，Haskell中对顺序数据最友好的数据结构是List

 data [a] = a:[a] | []

列表给你ϴ(1)缺点和模式匹配。标准库(就此而言是前奏)充满了有用的列表函数，这些函数会使你的代码杂乱无章(foldr，map，filter)。列表是坚持不懈，也就是纯函数式的，这非常好。Haskell列表并不是真正的“列表”，因为它们是共归纳的(其他语言称之为流)

ones :: [Integer]
ones = 1:ones


twos = map (+1) ones


tenTwos = take 10 twos

奇妙的工作。无限的数据结构震撼人心。

Haskell中的列表提供的接口很像命令式语言中的迭代器(因为惰性)。因此，它们被广泛使用是有道理的。

另一方面

列表的第一个问题是索引到它们(!!)需要ϴ(k)时间，这很烦人。另外，追加可能很慢++，但Haskell的惰性求值模型意味着，如果它们发生了，这些可以被视为完全平摊。

列表的第二个问题是它们的数据局部性很差。当内存中的对象不是相邻布局时，真正的处理器会产生很高的常量。因此，在c++中，std::vector具有比我所知道的任何纯链表数据结构更快的“snoc”(将对象放在末尾)，尽管这不是一个不如Haskell的列表友好的持久化数据结构。

列表的第三个问题是它们的空间效率很差。大量的额外指针会增加你的存储空间(以一个恒定的因素)。

序列是功能性的

Data.Sequence在内部基于手指的树木(我知道，你不想知道这个)，这意味着它们有一些很好的属性

  1. 纯粹的功能。Data.Sequence是一个完全持久化的数据结构。
  2. 快速访问树的开始和结束。ϴ(1)(平摊)来获取第一个或最后一个元素，或追加树。在列表最快的事情上，Data.Sequence最多是一个常数慢。
  3. (log n)对序列中间的访问。这包括插入值以生成新的序列
  4. 高品质原料药

另一方面，Data.Sequence并没有对数据局部性问题做太多的工作，并且只适用于有限的集合(它没有列表那么懒惰)

数组不适合胆小的人

数组是CS中最重要的数据结构之一，但它们不太适合懒惰的纯函数世界。数组提供了对集合中间的ϴ(1)访问和非常好的数据局部性/常量因素。但是，由于它们不太适合Haskell，使用起来很痛苦。在当前的标准库中，实际上有许多不同的数组类型。这些包括完全持久化的数组，用于IO单子的可变数组，用于ST单子的可变数组，以及上述的非盒装版本。更多信息请查看haskell wiki

Vector是一个“更好的”数组

Data.Vector包在更高级别和更干净的API中提供了所有数组的优点。除非你真的知道你在做什么，否则如果你需要类似数组的性能，你应该使用这些。当然，还是有一些需要注意的地方——像可变数组这样的数据结构在纯惰性语言中并不能很好地发挥作用。尽管如此，有时你想要O(1)性能，Data.Vector在一个可用的包中提供给你。

你还有其他选择

如果你只是想要列表能够有效地在末尾插入，你可以使用差异列表。列表搞砸性能的最好例子往往来自[Char]，前奏别名为String。Char列表很方便，但往往比C字符串慢20倍，所以可以随意使用Data.Text或非常快的Data.ByteString。我确信还有其他面向序列的库我现在没有想到。

结论

90+%的时间，我需要在Haskell列表中的顺序集合是正确的数据结构。列表就像迭代器，使用列表的函数可以很容易地与任何其他数据结构一起使用，使用它们附带的toList函数。在一个更好的世界里，前奏曲应该是完全参数化的，关于它使用的容器类型，但目前[]充斥着标准库。所以，在任何地方使用列表(几乎)都是没问题的 您可以获得大多数列表函数的全参数化版本(并且使用它们是高尚的)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

事实上，Data.Traversable定义了一个API，该API或多或少适用于任何“列表”。

不过，尽管你可以很好地编写全参数代码，但我们大多数人并不是这样，而是到处使用列表。如果你正在学习，我强烈建议你也这样做。

编辑:根据注释，我意识到我从未解释过什么时候使用Data.Vector vs Data.Sequence。数组和向量提供了极快的索引和切片操作，但基本上是瞬态(必需的)数据结构。像Data.Sequence和[]这样的纯函数式数据结构可以有效地从旧值生成新值，就好像你修改了旧值一样。

  newList oldList = 7 : drop 5 oldList

不修改旧的列表，也不需要复制它。所以即使oldList非常长，这个“修改”也会非常快。类似的

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence

将生成一个新序列，其中newValue for取代其3000元素。同样，它不会破坏旧的序列，它只是创建一个新的序列。但是，它做得非常有效，取O(log(min(k,k-n))其中n是序列的长度，k是要修改的下标。

你不能轻易地用Vectors和Arrays做到这一点。它们可以是修改，但这是真正的强制修改，所以不能在常规Haskell代码中完成。这意味着在Vector包中进行修改的操作，如snoc和cons，必须复制整个向量，因此需要O(n)时间。唯一的例外是，你可以在ST单子(或IO)中使用可变版本(Vector.Mutable)，并像在命令语言中一样进行所有修改。当你完成后，你“冻结”你的向量转换成你想用纯代码使用的不可变结构。

我的感觉是，如果列表不合适，你应该默认使用Data.Sequence。只有当你的使用模式不需要做很多修改，或者你需要在ST/IO单子中获得极高的性能时，才使用Data.Vector。

如果所有这些关于ST单子的讨论让你感到困惑:那就更有理由坚持使用纯粹的、快速的、漂亮的Data.Sequence。


提交答案