为什么Scala的"列表"被实现为链表

Question

我一直认为链表的好处是你可以添加或删除项目(特别是不是从最后),而不必复制很多元素,这要归功于指针之美.

但是,Scala List是不可变的(至少在默认情况下是这样).拥有不可变链表是有什么好处的(因为有明确的缺点,例如不是O(1)元素访问.)

谢谢!

Answer 1

我认为主要原因是链表的最强大用途之一是头/尾分裂.有很多递归算法看起来像这样:

def listlen[A](xs: List[A], already: Int = 0): Int = xs match {
  case Nil => already
  case x :: rest => listlen(rest, already+1)
}

当然,名单已经知道如何获得他们的长度; 这只是一个例子.关键是你拉下头部,然后用尾巴做其他事情 - 很多有用的东西都是这样的.

由于列表是不可变的,我们可以做其他事情 - 我们可以花费尽可能多的时间来评估列表的其余部分!我们不必一气呵成; 我们相信它永远不会改变.如果列表是可变的,则不会出现这种情况 - 我们需要锁定列表,阻止其他人看到它,或者我们需要制作整个事件的防御性副本,以防万一有人可能会交换它.

现在,如果你真的想要一个可变列表,那mutable.LinkedList就是你所讨论的具有很好的插入属性.但是,这并不能让您在不可变列表给您的情况下安心地进行优雅的递归.

(请注意,您可以使用不可变的数组支持结构执行此操作,但是包含每个元素的集合的可能好处是您不需要保存或复制整个数组,因为您需要一些元素来自结束;如果列表中的早期元素不再被指向,则可以对它们进行垃圾回收.)

LinkedList在当今的硬件上只是一种效率低下的数据结构,每个节点都是一个缓存缺失,没有什么比缓存未命中更昂贵. (5认同)
@bestsss - 取决于上下文.通常,是的,你是对的.从性能的角度来看,一定应该是链接列表的_suspicious_,除非它们使您更容易使用更有效的算法(例如"不需要制作大型数据集的防御性副本").但是硬件现在如此之快以至于很多任务都受到你正确编码能力的限制,而不是硬件快速运行它的能力.(但是我会批评链接列表在抱怨缓存未命中之前是不可并行化的.哦,并且页面错误仍然比缓存缺失更糟糕.) (3认同)

Answer 2

结构共享.如果在列表上执行高阶函数(map,fold等),则返回一个列表的新实例,该列表共享上一个列表的指针.

Daniel Spiewak上周在NE Scala做了关于功能数据结构的精彩演讲.见这里:http: //www.nescala.org/2011/

@aharon一个`java.util.ArrayList`永远不是一成不变的.你可以得到一个不可修改的_view_,但原始引用仍然能够改变它,所以库不能依赖它永远不会改变. (4认同)

Answer 3

但是，Scala的列表是不可变的（至少默认情况下）。拥有不可变的链表有什么好处

我在这里参加聚会有点晚了，但是我觉得没有人提出一个重要观点：

除了雷克斯·克尔（Rex Kerr）所说的那样，值得指出的是，通过在不可变的单链列表之前添加新列表是一项固定的时间操作。您只需创建一个指向已经存在的列表的新节点即可。由于列表是不可变的，因此您知道新的尾部将永远不会更改，并且您无需复制任何数据。

我怀疑您可以通过恒定的时间操作并以较小的内存占用量（仅一个节点的成本）构建新的，较大的但仍然不可变的列表，这实际上是选择数据结构的很大一部分原因。

Answer 4

scala.List是别名scala.collection.immutable.List.它只是众多具体集合实现中的一个.

如果你来自Java背景,等同java.util.List于scala.collection.mutable.Buffer,而不是scala.List.

您可以在Scala 2.8集合概述中概述集合库的结构..在这里,您将找到许多其他具体实现(可变和不可变).