Haskell列表的内部表示？
lim*_*imp 19 haskell list data-structures
哈斯克尔支持一些基本的操作,通过列表递归,比如head,tail,init和last.我在内部想知道Haskell如何表示其列表数据？如果它是单链表,那么随着列表的增长init,last操作可能会变得昂贵.如果它是一个双向链表,那么所有四个操作都可以O(1)很容易地完成,尽管会以一些内存为代价.无论哪种方式,对我来说都很重要,所以我可以编写适当的代码.(尽管,函数式编程的精神似乎是"问它是做什么,而不是它是怎么做的").
Don*_*art 28
列表表示为......单链表.定义如下:
data [] a = [] | a : [a]
你可以写成:
data List a = Empty | Cons a (List a)
内存布局完全由此定义.
- 构造函数是堆分配的
- 内部多态字段是指向其他已分配节点的指针
- 脊椎是懒惰的
所以你最终得到这样的东西:
所以head是O(1)在此结构中,同时last或(++)是O(n)的
Haskell中的数据结构没有神奇之处 - 它们的直接定义完全清楚了复杂性(模数懒惰).如果您需要不同的复杂性,请使用不同的结构(例如IntMap,Sequence,HashMap,Vector等)......
- 哦,我并不是说它"容易",只是说没有魔法.如果您只是查看数据类型定义,那么它们都是可派生的. (7认同)
- 谢谢你的回答.我不确定是否有必要强调这个答案应该是多么清晰/明显 - 我是Haskell的初学者,而且来自C它是一个巨大的变化,所以我还在搞清楚.无论如何,再次感谢. (3认同)
Chr*_*lor 14
Haskell的列表被单独联系,所以cons,head和tail是O(1),而init与last是O(Ñ).
如果您需要更好的性能,请考虑使用Data.Sequence中的Seq类型,它提供对列表两端的O(1)访问.在内部,它使用2-3个手指树.