Cons的优点是什么？

Question

许多函数式编程语言支持并推荐数据构造器Cons (对于(1, (2, (3)))之类的列表，如Haskell和Scala )。

但它的优势是什么呢？这样的列表既不能随机访问，也不能在O(1)中追加。

Answer 1

Cons (“构造”的缩写)不是一个数据结构，它是创建反单元格的操作的名称。通过将几个单元连接在一起，可以建立一个数据结构，特别是一个链接列表。讨论的其余部分假设正在使用cons操作创建链接列表。

虽然在头处添加O(1)是可能的，但通过索引随机访问元素是一项昂贵的操作，这需要遍历正在访问的元素之前的所有元素。

链接列表的优点？它是一种功能数据结构，在修改的情况下创建或重新创建很便宜；它允许在多个列表之间共享节点，并允许简单的垃圾收集。它非常灵活，有了正确的抽象，就可以表示其他更复杂的数据结构，如堆栈、队列、树、图。还有许多专门为操作列表而编写的过程--例如map、filter、fold等，它们使处理列表成为joy。最后，列表是递归数据结构，递归(特别是尾递归)是解决函数式编程语言中问题的首选方法，因此在这些语言中，使用递归数据结构作为主要数据结构是很自然的。

Answer 2

首先，让我们区分一下通常称为::的ML样式列表数据构造函数的昵称"cons“和最初的Lisp样式的cons函数的昵称来自什么。

在Lisps中，cons单元格是一种通用的数据结构，不限于同构元素类型的列表。在ML样式语言中，等效的是嵌套对或二元组，空列表由"unit“类型表示，通常编写为()。ofópez很好地概述了Lisp cons的实用性，因此我将在此保留它。

在大多数ML风格的语言中，不变的缺点列表的优点与它们在Lisps中的使用并没有太大的不同，它用动态类型的灵活性来换取静态类型的保证和ML样式模式匹配的语法。

然而，在Haskell，由于懒惰的评估，情况就大不相同了。构造函数是懒惰的，它们上的模式匹配是强制求值的为数不多的方法之一，因此与严格评估的语言相比，通常应该避免尾递归。相反，通过将递归调用放在列表的尾部，只有在需要时才能计算每个递归调用。如果使用map或foldr等适当的延迟函数来处理延迟生成的列表，则可以在常量内存中构造和使用一个大列表，以相同的速率强制尾部，这样GC就可以清除头部。

在Haskell中，一个常见的观点是，懒惰的反列表与其说是一种数据结构，不如说它是一种控制结构--一个与其他循环有效组合的具体化循环。

尽管如此，在很多情况下，反列表是不合适的--比如需要重复随机访问--在这种情况下，当然不推荐使用列表。