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

Question

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

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

有人可以在不深入了解数据结构的计算机科学理论的情况下解释列表、数组、向量、序列之间的区别吗？

另外，是否有一些常见的模式，您会使用一种数据结构而不是另一种数据结构？

是否有任何其他形式的数据结构我遗漏了并且可能有用？

Answer 1

列出摇滚

到目前为止，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 中的列表提供了一个很像命令式语言中的迭代器的接口(interface)(因为懒惰)。因此，它们被广泛使用是有道理的。

另一方面

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

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

列表的第三个问题是它们的空间效率很差。一堆额外的指针会增加你的存储空间(通过一个常数因子)。

序列是函数式的
Data.Sequence内部基于 finger trees (我知道，你不想知道这一点)这意味着它们有一些不错的特性

纯粹的功能。 Data.Sequence是一个完全持久化的数据结构。

该死的快速访问树的开头和结尾。 ϴ(1)(摊销)以获取第一个或最后一个元素，或附加树。在事物列表中最快的是，Data.Sequence最多是一个常数较慢。

ϴ(log n) 访问序列的中间。这包括插入值以生成新序列

优质原料药

另一方面， Data.Sequence对数据局部性问题没有太大作用，仅适用于有限集合(它不如列表懒惰)

阵列不适合胆小的人

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

Vector 是一个“更好”的数组
Data.Vector包以更高级别和更清晰的 API 提供了所有数组的优点。除非你真的知道你在做什么，否则如果你需要类似数组的性能，你应该使用这些。当然，一些警告仍然适用——像数据结构这样的可变数组在纯粹的惰性语言中表现不佳。尽管如此，有时您还是想要 O(1) 的性能，而 Data.Vector给你一个可用的包。

你还有其他选择

如果您只想要能够在末尾有效插入的列表，您可以使用 difference list .列表搞砸性能的最好例子往往来自 [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对比 Data.Sequence .数组和向量提供极快的索引和切片操作，但基本上是 transient (命令式)数据结构。纯函数式数据结构，如 Data.Sequence和 []让有效地从旧值生成新值，就像您修改了旧值一样。

  newList oldList = 7 : drop 5 oldList

不修改旧列表，也不必复制它。所以即使 oldList非常长，这种“修改”会非常快。同样

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

将产生一个带有 newValue 的新序列因为代替了它的 3000 个元素。同样，它不会破坏旧序列，它只是创建一个新序列。但是，它非常有效地执行此操作，取 O(log(min(k,k-n)) 其中 n 是序列的长度，k 是您修改的索引。

你不能用 Vectors 轻松做到这一点和 Arrays .它们可以被修改，但那是真正的命令式修改，因此不能在常规 Haskell 代码中完成。这意味着在 Vector 中的操作进行修改的软件包，如 snoc和 cons必须复制整个向量所以取 O(n)时间。唯一的异常(exception)是您可以在 Vector.Mutable 中使用可变版本( ST )。 monad(或 IO)并像使用命令式语言一样进行所有修改。完成后，您可以“卡住”您的向量以转换为您想要与纯代码一起使用的不可变结构。

我的感觉是你应该默认使用 Data.Sequence如果列表不合适。使用 Data.Vector仅当您的使用模式不涉及进行大量修改时，或者您需要在 ST/IO monad 中具有极高的性能时。

如果这一切都在谈论 ST monad 让你感到困惑:更有理由坚持纯粹的快速和美丽 Data.Sequence .