list - 当我们已经有列表时，为什么 Haskell 需要 Data.Sequence？

Question

List 是 Haskell 的默认数据类型，为什么还需要 Data.Sequence？Data.Seq 是否意味着可以随机访问的 C 样式数组？

如果是，我想这意味着 Data.Sequence 存储在固定的内存缓冲区中，因此是急切的评估类型。只是一个猜测，你会帮助纠正吗？谢谢。

Answer 1

列表类型是单链表。因此，前置，head并且tail都是 O(1)。但是，++左侧列表的大小为 O(n)。

相比之下，Data.Sequence是一棵平衡树，所以对它的大多数操作都是 O(log n)。这不如 O(1) 快，但可能快得多 O(n)。换句话说，您可以比列表更快地加入序列，但前置稍慢。

除此之外，两种数据结构都具有非常相似的属性。他们都很懒惰，他们都是参照透明的。（序列必须是有限的。）

另请参阅Data.Sequence 文档中的开场白：

通用有限序列。除了有限且具有严格的操作之外，序列在有效支持更广泛的操作方面也不同于列表。

这里显然描述了底层算法。（特别是，包括一个漂亮的图表。）

如果你想要数组，你需要查看Data.Array和/或Data.Vector。