列出了岩石

到目前为止，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的列表友好的持久化数据结构。

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

序列是功能性的

数据。序列在内部是基于手指树(我知道，你不想知道这个)，这意味着它们有一些很好的属性

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

另一方面，数据。序列对数据局部性问题没有太大帮助，并且只适用于有限的集合(它没有列表那么懒惰)

数组不适合胆小的人

Arrays are one of the most important data structures in CS, but they dont fit very well with the lazy pure functional world. Arrays provide ϴ(1) access to the middle of the collection and exceptionally good data locality/constant factors. But, since they dont fit very well into Haskell, they are a pain to use. There are actually a multitude of different array types in the current standard library. These include fully persistant arrays, mutable arrays for the IO monad, mutable arrays for the ST monad, and un-boxed versions of the above. For more check out the haskell wiki

Vector是一个“更好的”数组

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

你还有其他选择

如果您只是希望列表能够有效地在末尾插入，则可以使用差值列表。列表破坏性能的最佳例子来自[Char]，前奏别名为String。Char列表很方便，但运行速度往往比C字符串慢20倍，所以可以随意使用Data。Text或者非常快的data。bytestring。我确信还有其他面向序列的库我现在没有想到。

结论

90+% of the time I need a sequential collection in Haskell lists are the right data structure. Lists are like iterators, functions that consume lists can easily be used with any of these other data structures using the toList functions they come with. In a better world the prelude would be fully parametric as to what container type it uses, but currently [] litters the standard library. So, using lists (almost) every where is definitely okay. You can get fully parametric versions of most of the list functions (and are noble to use them)

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

事实上，是数据。可遍历定义了一个API，该API或多或少适用于任何“类似列表”的东西。

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

---

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

  newList oldList = 7 : drop 5 oldList

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

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

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

You cant easily do this with Vectors and Arrays. They can be modified but that is real imperative modification, and so cant be done in regular Haskell code. That means operations in the Vector package that make modifications like snoc and cons have to copy the entire vector so take O(n) time. The only exception to this is that you can use the mutable version (Vector.Mutable) inside the ST monad (or IO) and do all your modifications just like you would in an imperative language. When you are done, you "freeze" your vector to turn in into the immutable structure you want to use with pure code.

我的感觉是，您应该默认使用Data。如果列表不合适，则进行排序。使用数据。只有当你的使用模式不需要做很多修改，或者你需要在ST/IO单子中获得极高的性能时才使用向量。

如果所有这些关于ST单子的讨论让你感到困惑:那么更有理由坚持纯粹的快速和美丽的Data.Sequence。

列出了岩石

到目前为止，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的列表友好的持久化数据结构。

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

序列是功能性的

数据。序列在内部是基于手指树(我知道，你不想知道这个)，这意味着它们有一些很好的属性

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

另一方面，数据。序列对数据局部性问题没有太大帮助，并且只适用于有限的集合(它没有列表那么懒惰)

数组不适合胆小的人

Arrays are one of the most important data structures in CS, but they dont fit very well with the lazy pure functional world. Arrays provide ϴ(1) access to the middle of the collection and exceptionally good data locality/constant factors. But, since they dont fit very well into Haskell, they are a pain to use. There are actually a multitude of different array types in the current standard library. These include fully persistant arrays, mutable arrays for the IO monad, mutable arrays for the ST monad, and un-boxed versions of the above. For more check out the haskell wiki

Vector是一个“更好的”数组

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

你还有其他选择

如果您只是希望列表能够有效地在末尾插入，则可以使用差值列表。列表破坏性能的最佳例子来自[Char]，前奏别名为String。Char列表很方便，但运行速度往往比C字符串慢20倍，所以可以随意使用Data。Text或者非常快的data。bytestring。我确信还有其他面向序列的库我现在没有想到。

结论

90+% of the time I need a sequential collection in Haskell lists are the right data structure. Lists are like iterators, functions that consume lists can easily be used with any of these other data structures using the toList functions they come with. In a better world the prelude would be fully parametric as to what container type it uses, but currently [] litters the standard library. So, using lists (almost) every where is definitely okay. You can get fully parametric versions of most of the list functions (and are noble to use them)

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

事实上，是数据。可遍历定义了一个API，该API或多或少适用于任何“类似列表”的东西。

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

---

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

  newList oldList = 7 : drop 5 oldList

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

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

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

You cant easily do this with Vectors and Arrays. They can be modified but that is real imperative modification, and so cant be done in regular Haskell code. That means operations in the Vector package that make modifications like snoc and cons have to copy the entire vector so take O(n) time. The only exception to this is that you can use the mutable version (Vector.Mutable) inside the ST monad (or IO) and do all your modifications just like you would in an imperative language. When you are done, you "freeze" your vector to turn in into the immutable structure you want to use with pure code.

我的感觉是，您应该默认使用Data。如果列表不合适，则进行排序。使用数据。只有当你的使用模式不需要做很多修改，或者你需要在ST/IO单子中获得极高的性能时才使用向量。

如果所有这些关于ST单子的讨论让你感到困惑:那么更有理由坚持纯粹的快速和美丽的Data.Sequence。