Haskell：列表，数组，向量，序列
我正在学习Haskell并阅读了一些关于Haskell列表和（插入你的语言）列表的性能差异的文章。
作为一名学习者，我显然只是在不考虑性能差异的情况下使用列表。 我最近开始调查并发现了Haskell中的大量数据结构库。
有人可以解释列表，阵列，向量，序列之间的区别，而不会深入研究数据结构的计算机科学理论吗？
另外，是否有一些常见的模式可以使用一种数据结构而不是另一种？
是否还有其他任何形式的数据结构，我错过了并可能有用？
列出摇滚乐
到目前为止，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内部基于手指树（我知道，你不想知道这一点），这意味着他们有一些很好的属性
Data.Sequence是一个完全持久的数据结构。 Data.Sequence最多是一个不断变慢的。 另一方面， Data.Sequence对数据局部性问题没有太大作用，只对有限集合起作用（它比列表更懒惰）
阵列不适合心脏病
数组是CS中最重要的数据结构之一，但它们不适合懒惰的纯功能世界。 数组提供了对集合中间的Θ（1）访问和异常好的数据局部性/常数因子。 但是，由于它们不适合Haskell，所以它们很难使用。 实际上在当前标准库中有许多不同的数组类型。 这些包括完全持久性数组，IO monad的可变数组，ST monad的可变数组，以及上述的un-boxed版本。 更多检查haskell维基
向量是一个“更好”的数组
Data.Vector包在更高级别和更清洁的API中提供了所有数组的优点。 除非你真的知道你在做什么，否则你应该使用这些，如果你需要像数组一样的性能。 当然，一些注意事项仍然适用 - 像数据结构这样的可变数组只是不会在纯粹的懒惰语言中表现出色。 尽管如此，有时候你需要O（1）的性能，而Data.Vector会以可用包的Data.Vector给你。
你有其他选择
如果您只是希望能够在最后高效插入的列表，则可以使用差异列表。 列表搞砸性能的最好例子往往来自[Char] ，其前奏已被别名为String 。 Char列表比较容易理解，但倾向于比C字符串慢20倍，因此可以使用Data.Text或非常快速的Data.ByteString 。 我确信现在还没有其他序列导向库。
结论
我需要在Haskell列表中进行顺序收集的时间为90 +％是正确的数据结构。 列表就像迭代器，消耗列表的函数可以使用它们附带的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，它在任何“列表类似”事物中或多或少具有通用性。
尽管如此，尽管你可以做得很好，并且只写完全参数化的代码，但是我们大多数人并没有在整个地方使用它。 如果你正在学习，我强烈建议你也这样做。
编辑：基于评论我意识到我从来没有解释什么时候使用Data.Vector与Data.Sequence 。 数组和向量提供极其快速的索引和分片操作，但基本上是瞬态的（当务之急）数据结构。 像Data.Sequence和[]这样的纯功能数据结构可以高效地从旧值中生成新值，就像修改旧值一样。
newList oldList = 7 : drop 5 oldList
不会修改旧列表，也不必复制它。 所以即使oldList时间非常长，这个“修改”将会非常快。 同样
newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
将生成一个新的序列，其中包含3000个元素的newValue 。 同样，它不会破坏旧序列，它只是创建一个新序列。 但是，它是非常有效的，取O（log（min（k，kn）），其中n是序列的长度，k是你修改的索引。
你不能用Vectors和Arrays轻松做到这一点。 它们可以被修改，但这是真正必要的修改，所以不能在常规的Haskell代码中完成。 这意味着Vector程序包中的操作使得像snoc和cons这样的修改必须复制整个矢量，所以需要花费O(n)时间。 唯一的例外是你可以在ST monad（或IO ）中使用可变版本（ Vector.Mutable ），并且像在命令式语言中一样进行所有修改。 完成后，您可以“冻结”您的向量，将其转化为您想要与纯代码一起使用的不可变结构。
我的感觉是，如果列表Data.Sequence ，应该默认使用Data.Sequence 。 只有在您的使用模式不涉及进行很多修改时，或者您需要ST / IO单元中的极高性能时才使用Data.Vector 。
如果所有关于ST monad的讨论都让你感到困惑：所有更坚持纯快速美丽Data.Sequence 。