或者用另一种方式说,如果只有一个头指针,你会得到一个基本的,单链接的列表会带来什么样的好处？我能看到的尾指针的好处是:
与O(n)列表连接(其中n是左侧列表的长度？)相比,这两者都是相当方便的东西.丢弃尾指针有哪些优点？
小智 11
与许多其他功能性[-ish]语言一样,F#有一个缺点列表(术语最初来自LISP,但概念是相同的).在F#中,::运算符(或List.Cons)用于cons'ing:注意签名是‘a –> ‘a list –> ‘a list(参见掌握F#列表).
不要将cons-list与包含离散的第一个[/ last]节点的不透明Linked List实现混淆 - cons-list中的每个单元都是[不同]列表的开头!也就是说,"列表"只是从给定的 cons-cell 开始的单元链.
当以类似功能的方式使用时,这提供了一些优点:一个是所有"尾部"单元是共享的,并且因为每个cons-cell是不可变的("数据"可能是可变的,但这是一个不同的问题)没有改变"尾巴"细胞的方法,并且包含所有其他包含所述细胞的列表.
由于这种特性,[新]列表可以有效地建立-也就是说,他们并不需要一个副本-只需通过利弊 "ING在前面.此外,将列表解构为head :: tail- 再次,没有副本 - 也非常有效,这在递归函数中通常非常有用.
这种不可变属性通常不存在于[标准可变]双链接列表实现中,因为附加会增加副作用:内部"最后"节点(类型现在是不透明的)并且其中一个"尾部"单元格被更改.(有一些不可变的序列类型允许"有效的恒定时间"附加/更新,例如Scala中的immutable.Vector - 但是,这些是重量级对象,而不是一系列单元格的缺点'在一起.)
如上所述,缺点是缺点不适用于所有任务 - 特别是,创建一个新列表除了缺点是一个O(n)操作,fsvo n,并且为了更好(或更糟) )列表是不可变的.
我建议您创建自己的版本,concat以了解此操作是如何完成的.(文章为什么我爱F#:列表 - 基础知识涵盖了这一点.)
快乐的编码.
另请参阅相关文章:为什么你只能在功能语言中添加到列表中？
F#列表是不可变的,没有"append/concat"这样的东西,而只是创建新的列表(可能会重用旧列表的一些后缀).不可变性有许多优点,超出了这个问题的范围.(所有纯语言,大多数函数式语言都有这种数据结构,它不是F#主义.)
也可以看看
http://diditwith.net/2008/03/03/WhyILoveFListsTheBasics.aspx
它有很好的图片来解释事物(例如,为什么前面的消费比最后的不可变列表便宜).