为什么Scala列表没有大小字段？ [英] Why doesn't the Scala List have a size field?

问题描述

来自Java背景，我想知道为什么Scala中的 List 不具有大小字段像它的Java等价物 LinkedList 。毕竟，使用大小字段，您可以在常量时间确定列表的大小，所以为什么大小字段丢失？

Coming from a Java background, I'm wondering why List in Scala doesn't have a size field like its Java equivalent LinkedList. After all, with a size field you'll be able to determine the size of the list in constant-time, so why was the size field dropped?

（这个问题指的是Scala 2.8和更高版本中的新集合类。另外，我指的是不可变的列表，而不是可变的。）

(This question refers to the new collection classes in Scala 2.8 and later. Also, I'm referring to the immutable List, not the mutable one.)

推荐答案

不能说大小字段是丢弃，因为没有大小的列表已经存在了50年，因为LISP在它们无所不在他们在ML和Haskell中也很常见，在scala中都有影响力。

One cannot say the size field was dropped, as such list without the size have existed for 50 years since LISP where they are ubiquitous and they are very common in ML and Haskell too, both influential in scala.

基本原因是列表是递归结构。一个非空的列表是 Cons（head：A，tail：List [A]） - 除了 Cons 实际上被称为 :: 以允许方便的中缀符号。您可以访问尾部（没有其头元素的列表），也是列表。这一切都是在所有的时间完成的。所以列表中的计数并不意味着只添加一个整数，而是像元素一样多的整数。这是可行的，但肯定不是免费的。

The basic reason is that list is a recursive structure. A non empty List is Cons(head: A, tail: List[A]) — except that Cons is in fact called :: to allow a convenient infix notation. You can access the tail (the list without its head element) and that is a list too. And this is done just about all the time. So having the count in the list would not mean adding just one integer, but as many integers as there are elements. This is feasible, but certainly not free.

如果您与java的 LinkedList 进行比较， LinkedList 一个递归的实现（基于节点，它或多或少像缺点，但是在两个方向上都有链接）。但是LinkedList不是一个Node，它拥有它们（并保留他们的计数）。所以当它有一个递归的实现，你不能递归地对待它。您希望LinkedList的尾部作为LinkedList，您将不得不删除头部并更改列表，或者将所有尾部元素复制到新的LinkedList。所以scala的列表和java的 LinkedList 是非常不同的结构。

If you compare with java's LinkedList, LinkedList has a recursive implementation (based on Node, which is more or less like Cons, but with links in both direction). But a LinkedList is not a Node, it owns them (and keep their count). So while it has a recursive implementation, you cannot treat it recursively. It you wanted the tail of a LinkedList as a LinkedList, you would have to either remove the head and have your list changed or else copy all the tail elements to a new LinkedList. So scala's List and java's LinkedList are very different structures.

这篇关于为什么Scala列表没有大小字段？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！