为什么将Scala的“列表"实现为链接列表 [英] 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 {
  case Nil => already
  case x :: rest => listlen(rest, already+1)
}

当然，列表已经知道如何获取它们的长度.这只是一个例子.关键是要拔掉头，然后再用尾巴做一些其他事情，很多有用的事情都是这样工作的.

由于列表是不可变的，因此我们可以做其他事情-我们需要花费尽可能多的时间来评估列表的其余部分！我们不必一go而就.我们确信它永远不会改变.如果该列表是可变的，则不是这种情况；要么我们需要锁定列表，以防止其他人看到它，要么我们需要对整个内容进行防御性复制，以防万一有人交换它. >

现在，如果您真的想要一个可变列表，则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的“列表"实现为链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！