Why does Scala's toSeq convert an immutable Set to a mutable ArrayBuffer?

Question

If I call toSeq on an immutable Set collection I get an ArrayBuffer.

scala> Set(1,2,3).toSeq // returns Seq[Int] = ArrayBuffer(1, 2, 3)

This surprises me. Given Scala's emphasis on using immutable data structures, I expect to get back an immutable sequence like a Vector or List instead of a mutable ArrayBuffer. The returned ordering of the set elements should of course be undefined, but there doesn't seem to be any semantic reason why that ordering should also be mutable.

In general, I expect Scala operations to always produce immutable results unless I explicitly request a mutable one. This has been my assumption all along, but it is an incorrect one here, and I actually just spent an hour debugging a problem where the unexpected presence of an ArrayBuffer led to a runtime error in a match statement. My fix was to change Set(...).toSeq to Set(...).toList, but this feels like a hack because there's nothing about my application that requires a list in particular at that point.

Is having Set(...).toSeq return a mutable object a flaw in Scala's implementation, or is there a principle I am misunderstanding here?

This is Scala 2.9.2.

Answer 1

Here is the recent thread on whether Seq should mean immutable.Seq.

Roland Kuhn:

collection.Seq not having mutators is not at all a valid defense!

The example of mutable varargs is rather sneaky.

Recently,

scala> Set(1,2,3)
res0: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> res0.toSeq
res1: Seq[Int] = ArrayBuffer(1, 2, 3)

scala> res0.to[collection.immutable.Seq]
res2: scala.collection.immutable.Seq[Int] = Vector(1, 2, 3)

Answer 2

I agree it's a little strange, but I do not believe it is a flaw. First, consider this: the compile-time type of Set.toSeq is

() => Seq[Int]

not

() => ArrayBuffer[Int]

ArrayBuffer just happens to be the run-time type of the returned object (probably because Set.toSeq adds to an ArrayBuffer and then just returns that without converting).

So, even though toSeq is giving you back a mutable object, you can't actually mutate it (without casting, or pattern matching to ArrayBuffer -- so the real "strange" part is that Scala lets you pattern match on arbitrary classes). (You have to trust that Set doesn't hold on to the object and mutate it, but I think that's a fair assumption to make).

Another way to look at it is, a mutable type is just strictly more specific than an immutable type. Or, another way of saying this is, every mutable object can also be treated as an immutable object: an immutable object has a getter, and a mutable object has a getter and a setter -- but it still has a getter.

Of course, this can be abused:

val x = new Seq[Int] {
    var n: Int = 0
    def apply(k: Int) = k
    def iterator = {
        n += 1
        (0 to n).iterator
    }
    def length = n
}

x foreach println _
0
1

x foreach println _
0
1
2

but, well, so can a lot of things.