Haskell列表的内部表示？
Haskell列表的内部表示？
提问于 2013-02-25 16:47:09
Haskell支持列表递归的一些基本操作，如head、tail、init和last。我想知道，在内部，Haskell是如何表示其列表数据的？如果它是一个单链表，那么随着链表的增长，init和last操作可能会变得代价高昂。如果它是一个双向链表，那么所有四个操作都可以很容易地进行O(1)，尽管要以一些内存为代价。无论哪种方式，知道这一点对我来说都很重要，这样我就可以编写适当的代码。(尽管函数式编程的精神似乎是“问它做了什么，而不是它是如何做的”)。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-02-25 16:51:57
列表表示为...单链表。该定义由以下定义给出：
data [] a = [] | a : [a]你可以这样写：
data List a = Empty | Cons a (List a)内存布局完全由此定义。
脊椎构造函数是堆allocated
- Internal多态字段是指向其他已分配节点的指针
- is
所以你最终会得到这样的结果：
所以head在这个结构上是O(1)，而last或(++)是O(n)
Haskell中的数据结构没有什么神奇之处--它们直接的定义清楚地表明了复杂性是什么(模惰性)。如果你需要不同的复杂度，可以使用不同的结构(如IntMap，Sequence，HashMap，Vector等)……
Stack Overflow用户
发布于 2013-02-25 16:50:23
哈斯克尔列表是单链的，所以cons，head和tail是O(1)，而init和last是O(n)。
如果需要更好的性能，可以考虑使用Data.Sequence中的Seq类型，它提供了对列表两端的O(1)访问。在内部，它使用2-3 finger trees。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15063115
复制相关文章
相似问题