Scala Collections inconsistencies

Question

Why is there a lack of consistency between Sets and Lists in Scala Collections API?

For example, there is immutable Set, but also a mutable one. If I want to use the latter, I can simply do this:

val set = Set[A]()
set += new A

However, there is no mutable List, per se. If I want to write a similar code snippet using Lists, which data structure to use? LinkedList sounds as a good candidate, because it is mutable, but has no += method defined. ListBuffer seems to satisfy the requirements, but it is not a list.

After reading 2.8 Collections docs I come to the conclusion MutableList is probably the best fit.

I still somehow wish there was scala.collection.mutable.List.

Answer 1

The reason for this is that Java has co-opted the functional List type to mean something that it is not (i.e. java.util.List is not a list).

It probably makes no sense for a functional programming language to have a mutable List as such a type is an oxymoron. Hence ListBuffer or ArrayBuffer. Or just use IndexedSeq, of which there are mutable and immutable implementations

Answer 2

The sequence/list analogue of Set in Scala's collection libraries is Seq. List is just a particular, immutable implementation of Seq, as is Vector. ArrayBuffer or ListBuffer are typical implementations of mutable.Seq.

Answer 3

ArraySeq may be what you are looking for, except += is exceptionally slow. You could also use a java.util.ArrayList and import collection.JavaConversions._

It seems Scala lacks a good mutable List-like collection with constant time index (like ArrayList for java).

In any case, note that "List" refers to exactly the type "scala.immutable.List". Therefore Seq (or some other more abstract collection type), is the type you should expect in methods rather than "List" if you want to generalize over immutable/mutable collections.

More ideal is requring an IndexedSeq, which sort of means that the index operation is performant for that collection. However, I'm not sure ListBuffer falls into that category.

Answer 4

Because Set is just a trait -- it is abstract and requires an implementation. So one can speak of classes which are mutable.Set or immutable.Set.

Meanwhile, List is a class, an implementation of the (abstract) trait immutable.LinearSeq. There can never be any other class which is also a List. You'll find out, however, that there is a mutable.LinearSeq trait.

In Java terms, you are comparing interfaces with classes -- they are distinct.

Answer 5

Don't forget scala.collection.mutable.{LinkedList,DoubleLinkedList}. They are mutable, and they are LinearSeq. Mutation is a little weird--you can modify the head by assigning to the elem reference, and the tail by assigning to the next reference.

For example, this loop changes all negative values to zero.

val lst = collection.mutable.LinkedList(1, -2, 7, -9)
var cur = lst
while (cur != Nil) { 
  if (cur.elem < 0) cur.elem = 0
  cur = cur.next 
}

This loop removes every second element from the list.

var cur = lst
while (cur != Nil && cur.next != Nil) { 
  cur.next = cur.next.next
  cur = cur.next 
}

I am not suggesting that these are any better than the immutable List. I am just pointing out that Scala has mutable lists that look fairly similar to what you have seen in your data structures class.