list - Haskell 列表的内部表示？

Question

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

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 等)...