Lai*_*uan 4 functional-programming data-structures
许多函数式编程语言都支持并推荐数据构造函数Cons(对于像Haskell和Scala(1, (2, (3)))这样的列表.
但它的优点是什么？这些列表既不能随机访问,也不能附加到其中O(1).
Cons("构造"的简写)不是数据结构,它是创建cons-cell的操作的名称.并且通过将几个单元链接在一起,可以构建数据结构,尤其是链接列表.讨论的其余部分假设正在使用操作创建链接列表.cons
虽然可以在头部附加O(1),但是通过索引随机访问元素是一项代价高昂的操作,需要遍历所访问的元素之前的所有元素.
链表的优点是什么？它是一个功能数据结构,在修改时创建或重新创建便宜; 它允许在几个列表之间共享节点,并允许轻松垃圾收集.它非常灵活,通过正确的抽象,可以表示其他更复杂的数据结构,如堆栈,队列,树,图.而且有专门为处理列表写了很多,很多程序-例如map,filter,fold等,使操作列表喜悦.最后,列表是递归数据结构,递归(特别是尾递归)是解决函数式编程语言中问题的首选方法; 所以在这些语言中,将递归数据结构作为主要数据结构是很自然的.