Haskell：列表，数组，向量，序列
我正在学习Haskell，并阅读了一些关于Haskell列表和（插入你的语言）数组的性能差异的文章。
作为学习者，我显然只是使用列表，甚至不考虑性能差异。 我最近开始调查，发现了Haskell中的大量数据结构库。
有人可以解释列表，arrays，向量，序列之间的差异，而不会深入数据结构的计算机科学理论？
另外，有一些常见的模式，你会使用一个数据结构，而不是另一个？
还有什么其他forms的数据结构，我错过了，可能是有用的？
列出摇滚乐
到目前为止，Haskell中序列数据最友好的数据结构就是List
data [a] = a:[a] | [] 列表给你Θ（1）缺点和模式匹配。 标准库，就此而言，前奏，充满了有用的列表函数，应该抛弃你的代码（ foldr ， map ， filter ）。 列表是持久的 ，又名纯粹的function，这是非常好的。 Haskell列表不是真正的“列表”，因为它们是合作的（其他语言称为这些stream），所以类似的东西
ones :: [Integer] ones = 1:ones twos = map (+1) ones tenTwos = take 10 twos
奇妙的工作。 无限的数据结构摇滚。
Haskell中的列表提供了一个非常像命令式语言中的迭代器的接口（因为懒惰）。 所以，它被广泛使用是有道理的。
另一方面
列表的第一个问题是要索引它们(!!)需要Θ（k）时间，这是令人讨厌的。 另外，追加可以是慢的++ ，但是Haskell的懒惰评估模型意味着如果它们发生，它们可以被视为完全摊销。
列表中的第二个问题是它们的数据局部性较差。 当内存中的对象没有相邻排列时，真正的处理器会产生很高的常量。 因此，在C ++中， std::vector与我所知的任何纯链表数据结构相比，具有更快的“snoc”（将对象放在最后），尽pipe这不是一个持久的数据结构，不如Haskell的列表友好。
列表中的第三个问题是空间效率不高。 一堆额外的指针推动你的存储（按一个常数）。
序列是function的
Data.Sequence是内部基于手指树 （我知道，你不想知道这一点），这意味着他们有一些不错的属性
- 纯粹的function。
Data.Sequence是一个完全持久的数据结构。 - 快速访问树的开始和结束。 Θ（1）（摊销）得到第一个或最后一个元素，或者追加树。 在事物列表最快的时候，
Data.Sequence最多是一个不变的慢。 - Θ（log n）访问序列的中间部分。 这包括插入值来创build新的序列
- 高品质的API
另一方面， Data.Sequence对于数据局部性问题并没有太多的作用，只对有限的集合起作用（它比列表更懒惰）
arrays并不是因为心灵的模糊
数组是CS中最重要的数据结构之一，但它们与懒惰的纯function性世界并不相配。 数组提供Θ（1）访问集合的中间和exception好的数据局部性/常数因子。 但是，由于他们不适合Haskell，他们是一个痛苦的使用。 实际上在当前标准库中有许多不同的数组types。 这些包括完全持久性数组，IO monad的可变数组，ST monad的可变数组，以及上述的un-boxed版本。 更多检查haskell维基
向量是一个“更好”的数组
Data.Vector包提供了更高级别和更清洁的API中所有数组的优点。 除非你真的知道自己在做什么，如果你需要像数组一样的performance，你应该使用这些。 当然，一些注意事项仍然适用 – 像数据结构这样的可变数组只是不会在纯粹的懒惰语言中performance出色。 尽pipe如此，有时候你需要这个O（1）的性能，而Data.Vector会给你一个可用的包。
你有其他的select
如果您只想列出能够在最后高效插入的列表，则可以使用差异列表 。 列表搞砸了性能的最好例子往往来自[Char] ，其前奏已被别名为String 。 Char列表很容易，但是往往比Cstring慢20倍，因此可以使用Data.Text或非常快的Data.ByteString 。 我确定还有其他序列导向库，我现在没有想到。
结论
我需要在Haskell列表中顺序收集的时间为90 +％是正确的数据结构。 列表就像迭代器，消耗列表的函数可以很容易地使用任何其他数据结构，使用它们toList函数。 在一个更美好的世界里，前奏对于它使用的是什么样的容器types是完全参数化的，但是现在却抛弃了标准库。 所以，使用列表（几乎）每一个地方肯定是好的。
您可以获得大部分列表函数的完全参数化版本（并且使用它们是高贵的）
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定义了一个或多或less具有通用性的API，像“list like”一样。
尽pipe如此，尽pipe你可以很好地写出完全参数化的代码，但是我们大多数人并不是全部使用列表。 如果你正在学习，我强烈build议你也这样做。
编辑：基于评论，我意识到我从来没有解释什么时候使用Data.Vector与Data.Sequence 。 数组和向量提供极其快速的索引和切片操作，但基本上是瞬态的（势在必行）数据结构。 像Data.Sequence和[]这样的纯function数据结构可以高效地从旧值中生成新值，就像修改旧值一样。
newList oldList = 7 : drop 5 oldList
不会修改旧的列表，也不必复制它。 所以，即使oldList非常长，这个“修改”将会非常快。 同样
newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
将产生一个新的序列，其中3000个元素的地方是一个newValue 。 同样，它不会破坏旧的序列，它只是创build一个新的序列。 但是，它是非常有效的，取O（log（min（k，kn）），其中n是序列的长度，k是修改的索引。
你不能用Vectors和Arrays轻松做到这一点。 他们可以被修改，但这是真正的势在必行的修改，所以不能在常规的Haskell代码中完成。 这意味着Vector程序包中的操作使得像snoc和cons这样的修改必须复制整个vector，所以需要花费O(n)时间。 唯一的例外是你可以使用ST monad（或者IO ）里面的可变版本（ Vector.Mutable ），并且像命令式语言那样做所有的修改。 完成后，您可以“冻结”您的向量，将其转化为纯代码使用的不可变结构。
我的感觉是，如果列表Data.Sequence ，应该默认使用Data.Sequence 。 只有在您的使用模式不需要进行很多修改，或者您需要ST / IO monad内的非常高的性能时，才使用Data.Vector 。
如果说ST单子的这一切都让你感到困惑：所有理由都坚持纯粹快速而美丽的Data.Sequence 。
