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)。换句话说，您可以比列表更快地连接序列，但 prepend 稍微慢一些。

除此之外，这两种数据结构具有非常相似的属性；他们都是懒惰的，他们都是引用透明的。 (尽管序列必须是有限的。)

另请参阅 the documentation for Data.Sequence 的开场白:

General purpose finite sequences. Apart from being finite and having strict operations, sequences also differ from lists in supporting a wider variety of operations efficiently.

底层算法显然是 described here 。 (特别是，包括一个漂亮的图表。)

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