data-structures - 缺点是什么？

Question

许多函数式编程语言支持并推荐数据构造函数Cons（对于像Haskell和Scala(1, (2, (3)))这样的列表） 。

但它的优点是什么？这样的列表既不能随机访问，也不能附加到 in 中O(1)。

Answer 1

Cons（“构造”的简写）不是数据结构，它是创建cons-cell的操作的名称。通过将几个单元链接在一起，可以构建一个数据结构，特别是一个链表。其余的讨论假设一个链表是用操作创建的。cons

尽管可以在头部追加 O(1)，但通过索引随机访问元素是一项代价高昂的操作，这需要在被访问的元素之前遍历所有元素。

链表的优点？它是一种功能性数据结构，在修改的情况下创建或重新创建成本低；它允许在多个列表之间共享节点，并且可以轻松进行垃圾收集。它非常灵活，通过正确的抽象可以表示其他更复杂的数据结构，例如堆栈、队列、树、图。并且有很多很多专门为处理列表而编写的程序——例如map、filter、fold等，它们使处理列表变得很有趣。最后，列表是递归的数据结构和递归（特别是尾递归）是解决函数式编程语言问题的首选方式；所以在这些语言中，将递归数据结构作为主要数据结构是很自然的。

Answer 2

首先，让我们区分“cons”作为通常调用的 ML 风格的列表数据构造函数::的昵称和这个昵称的来源，原始 Lisp 风格的cons函数。

在 Lisps 中，cons 单元格是一种通用数据结构，不限于同类元素类型的列表。ML 风格语言中的等价物将是嵌套对或 2 元组，空列表由通常编写的“单元”类型表示()。Óscar López 很好地概述了 Lisp 的实用性cons，所以我将把它留在那里。

在大多数 ML 风格的语言中，不可变 cons 列表的优点与它们在 Lisps 中的列表使用并没有太大区别，牺牲了动态类型的灵活性来保证静态类型和 ML 风格的模式匹配的语法。

然而，在 Haskell 中，由于惰性求值，情况就大不相同了。构造函数是惰性的，对它们进行模式匹配是强制求值的少数方法之一，因此与严格求值的语言相比，通常情况下应该避免尾递归。相反，通过将递归调用放在列表的尾部，可以仅在需要时计算每个递归调用。如果使用适当的惰性函数（如mapor ）处理延迟生成的列表foldr，则可以在常量内存中构造和消耗一个大列表，并且尾部以与头部被丢弃以供 GC 清理的速度相同的速率强制执行。

Haskell 中的一个常见观点是惰性 cons 列表与其说是一种数据结构，不如说是一种控制结构——一个与其他此类循环有效组合的具体循环。

也就是说，在很多情况下 cons 列表是不合适的——例如当需要重复随机访问时——在这些情况下当然不建议使用列表。