list - Haskell 列表的内部表示？

Question

Haskell 支持通过列表进行递归的一些基本操作，例如head、和。我想知道，在内部，Haskell 如何表示其列表数据？如果它是一个单链表，那么随着列表的增长，操作可能会变得昂贵。如果它是一个双向链表，那么所有四个操作都可以很容易地完成，尽管会以一些内存为代价。无论哪种方式，知道这一点对我来说很重要，这样我才能编写适当的代码。（虽然，函数式编程的精神似乎是“问它做什么，而不是它是怎么做的”）。tailinitlastinitlastO(1)

Answer 1

列表表示为 ... 单链表。定义由下式给出：

data [] a = [] | a : [a]

你可以写成：

data List a = Empty | Cons a (List a)

内存布局完全由此定义。

• 构造函数是堆分配的
• 内部多态字段是指向其他已分配节点的指针
• 脊椎很懒

所以你最终会得到这样的结果：

head在这个结构上O(1)也是如此，而lastor(++)是O(n)

Haskell 中的数据结构没有魔法——它们直接的定义完全清楚地说明了复杂性是什么（模惰性）。如果您需要不同的复杂度，请使用不同的结构（例如 IntMap、Sequence、HashMap、Vector 等）...

Answer 2

Haskell 列表是单链接的，所以cons和head是tailO(1)，而init和last是 O( n )。

如果您需要更好的性能，请考虑使用Data.SequenceSeq中的类型，它提供对列表两端的 O(1) 访问。在内部它使用2-3 个手指树。