Why doesn't the Scala List have a size field?

Question

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?

(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.)

Solution 1

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.

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.

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.

Solution 2

Because maintaining this field would

1. Add memory overhead to all lists;
2. Add slight time overhead on every list creation.

In Java normally a LinkedList is created, and then manipulated without creating new lists by adding/removing elements; in Scala there are many Lists created.

So it was decided that the overhead isn't worth it.

Solution 3

The "disadvantage" of O(n) complexity is not as big as you might think. Martin Odersky mentioned in a talk that (if I remember correctly) 90% of all lists created in all programs in any computer language have a size of 4 or less. (This was in the context of immutability and efficiency)

Therefore, O(n) access time for size is not such a big overhead for most lists created, and, as others have mentioned here, memory savings more than compensates for this.

Solution 4

List defines size :

> List(1, 2, 3).size
res4: Int = 3

which has linear o(n) execution time. If you really need a constant time, you should consider the mutable ListBuffer that provides a constant time size implementation.

Solution 5

Have you checked the length field?

View more solutions

Comments

[kapex]

It's size() in Java, a function.

[Didier Dupont]

But the function is backed by a field, which makes it O(1). Scala List has no such field, for good reason, but that makes accessing the length O(n).

[huynhjl]

"python dude" comes from a Java background? python doesn't refer to the language, does it?

[python dude]

@huynhjl: Am I not allowed to have more than one background? ;-)

[Mechanical snail]

@huynhjl: No. It means he's a male python.

[Tomasz Nurkiewicz]

length is a method thst traverses the whole list, hence having O(n) complexity. The OP asks why there is no length field with constant time access.

[python dude]

@Udo Held: Your link is from Scala 2.7.7, which I have no experience with. My question is based on Scala 2.9+, and specifically on the book "Programming in Scala", 2nd Ed., where it's stated in chapter 16 that determining the length of a List is linear in the number of elements.

[python dude]

Which version of Scala is this? Before or after 2.8?

[Udo Held]

scala-lang.org/api/current/scala/collection/mutable/… has the length as well and is 2.9. You will find size there as well which is equivalent to length.

[David]

at least since 2.8 and later. See : scala-lang.org/api/2.8.0/scala/collection/immutable/List.htm‌​l

[Admin]

Is this constant-time though? it says "equivalent of length"

[Didier Dupont]

I think the question referred to the immutable List, which is the default one in scala. It has no length field

[David]

In fact your are right. List has linear o(n) size execution time has we can see on the code : lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_0_1/src/‌​/…

[Daniel C. Sobral]

In fact, adding a size field would double the size of a cons from 8 to 16 bytes, given that objects are allocated in multiples of 8 bytes.

[David]

exact but it's a o(n) size implementation. The subject was that LinkedList java implementation have a size field that returs the size in constant time.

[ches]

FWIW immutable Vector is an indexed data structure with efficient length (among other indexed operations)—so there are alternatives to sacrificing immutability if you have no other good reason to do so.

[ayvango]

Lists are strict in scala. So every time Cons applied it knows size of the tail and so can increase by 1 and write it to a specific field. Like Cons(head : A, tail : List[A]) { override val size : Int = tail.size + 1}. It is possible, but may be considered too space hungry.