Haskell列表的内部表示？

Question

Haskell支持一些基本的列表递归操作，比如head、tail、init和last。我想知道Haskell是如何表示其列表数据的？如果它是一个单向链表，那么init和last操作可能会随着列表的增长而变得昂贵。如果它是一个双向链表，所有四个操作都可以很容易地实现O(1)，但代价是一些内存。无论哪种方式，这对我来说都很重要，这样我就可以编写适当的代码。(尽管函数式编程的精神似乎是“问它做了什么，而不是它是如何做到的”。)

- limp_chimp

---

询问它做什么，而不是如何做到这一点。但如果你关心编写相对快速的代码的话，就不要这样做 ;) - Niklas B.

那就是我的想法 :-) 所以我问了这个问题。 - limp_chimp

如果它是一个双向链表，那么这四个操作都可以很容易地做到O(1)。但是，如果你想保持纯函数式，那就不是那么容易了，因此在Haskell中普通的双向链表并不常用。要在保持纯函数式的同时以O(1)完成所有这些操作，需要更复杂的数据结构——然而，通过利用Haskell的惰性求值，你可以在其单向链表上实现比任何过程式语言都更好的O(1)操作（或者以某种分摊O(n)的方式，这几乎一样好）。 - leftaroundabout

Answer 1

列表用单向链表表示。定义如下：

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

你可以写成：

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

这完全由内存布局定义。

• 构造函数是堆分配的
• 内部多态字段是指向其他分配节点的指针
• 脊柱是惰性的

因此，最终会得到类似于以下内容：

所以这个结构的head是O(1)，而last或(++)是O(n)。

在Haskell中，数据结构没有什么神奇之处——它们的直接定义清楚地说明了复杂度是多少（除了惰性计算）。如果需要不同的复杂度，请使用不同的结构（例如IntMap、Sequence、HashMap、Vector等）。

- Don Stewart

---

谢谢您的回答。我不确定是否有必要强调这个答案应该是多么清晰/明显 - 我是Haskell的初学者，从C语言转来，这是一个巨大的变化，所以我仍在摸索中。无论如何，再次感谢。 - limp_chimp

哦，我并不是说这很“容易”，只是没有什么魔法。如果你仅仅看一下数据类型定义，所有的东西都可以推导出来。 - Don Stewart

两个重要的注意事项：惰性和融合。惰性意味着，例如，在 xs ++ ys 中，只有在遍历结果列表时才需要付出追加的代价；head (xs ++ ys) 是 O(1)，而不是 O(n)。融合意味着许多操作不会产生额外的开销，超过了遍历的开销；例如，map (*2) (xs ++ ys) 的成本比 map (*2) 和 ++ 的成本之和要低，因为 GHC 消除了产生的中间列表。 - Luis Casillas

Answer 2

Haskell列表是单向链接的，因此cons，head和tail的时间复杂度为O(1)，而init和last的时间复杂度为O(n)。

如果需要更好的性能，请考虑使用Data.Sequence中的Seq类型，它提供对列表两端的O(1)访问。内部使用2-3 finger trees。

- Chris Taylor