为什么 Scala 的 `Lists` 实现为链表 [英] Why are Scala's `Lists` implemented as linked lists

问题描述

我一直认为链表的好处是你可以添加或删除项目(尤其不是从末尾)，而无需复制大量元素，这要归功于指针的美妙.

然而，Scala 的 List 是不可变的(至少在默认情况下).拥有不可变链表有什么好处(因为有一定的缺点，例如不是 O(1) 元素访问.)

谢谢！

解决方案

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

def listlen[A](xs: List[A], already: Int = 0): Int = xs match {情况为零 =>已经案例 x :: 休息 =>听(休息，已经+1)}

当然，列表已经知道如何获得它们的长度；这只是一个例子.关键是你把头部拉下来，然后用尾部做其他事情——很多有用的东西都是这样工作的.

由于列表不可变，我们可以做其他事情——我们可以花尽可能多的时间来评估列表的其余部分！我们不必一口气完成；我们确信它永远不会改变.如果列表是可变的，情况就不会如此——要么我们需要锁定列表，防止其他人看到它，要么我们需要制作整个内容的防御性副本，以防万一有人可能会交换它.

现在，如果你真的想要一个可变列表，mutable.LinkedList 有你所说的很好的插入属性.但这并不能像不可变列表那样让您安心地进行优雅的递归.

(请注意，您可以使用不可变的数组支持结构来完成其中的一些操作，但是包含每个元素的集合的可能好处是您不需要保存或复制整个数组，因为您需要一个末尾的几个元素；如果不再指向列表中的早期元素，则它们可以被垃圾收集.)

I always thought that the benefit of linked lists was that you could add or remove items (especially not from the end) without having to copy lots of elements thanks to the beauty of pointers.

However, Scala's List is immutable (at least by default). What is the benefit of having an immutable linked list (because there are definite downsides, e.g. not O(1) element access.)

Thanks!

解决方案

I think the main reason is that one of the most powerful uses of linked lists is head/tail splitting. There are lots of recursive algorithms that look like this one:

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

Of course, lists already know how to get their length; this is just an example. The point is that you pull off the head, and then do something else with the tail--lots of useful things work this way.

Since lists are immutable, we can do something else--we can take as much time as we want to evaluating the rest of our list! We don't have to finish in one go; we're sure it will never change. This would not be the case if the list were mutable--either we need to lock the list, preventing anyone else from seeing it, or we need to make a defensive copy of the whole thing just in case someone might swap it.

Now, if you really want a mutable list, there's mutable.LinkedList that has the nice insertion properties that you're talking about. But that doesn't give you the elegant recursion with peace of mind that the immutable lists give you.

(Note that you could do some of this with an immutable array-backed structure, but the possible benefit of a collection with each element wrapped is that you don't need to save or copy the whole array just because you need a few elements from the end; if the early elements in the list aren't pointed to any more, they can be garbage collected.)

这篇关于为什么 Scala 的 `Lists` 实现为链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！