mutable vs. immutable in Scala collections

Question

I am fairly new to Scala and am trying to understand the collections hierarchy. I see that there is a distinction between 'mutable' and 'immutable' collections, but I don't understand what this actually means at the implementation level and how this relates to val and var. Can anyone give me some insight on this? Also, does every collection class have a 'mutable' version and an 'immutable' version, or are there some classes which can only be 'mutable' or 'immutable'?

Solution 1

Mutable means you can alter the collection in-place. So, if you have a collection c and you append an element with +=, then c has changed, and so has every other reference to that collection.

Immutable means that the collection object never changes; instead, you build new collection objects with operations such as + or ++, which return a new collection. This is useful in concurrent algorithms, since it requires no locking to add something to a collection. It may come at the cost of some overhead, but this property can be very useful. Scala's immutable collections are fully persistent data structures.

The difference is very similar to that between var and val, but mind you:

1. You can modify a mutable collection bound to a val in-place, though you can't reassign the val
2. you can't modify an immutable collection in-place, but if it's assigned to a var, you can reassign that var to a collection built from it by an operation such as +.

Not all collections necessarily exist in mutable and immutable variants; the last time I checked, only mutable priority queues were supported.

Solution 2

Immutable means unchangeable. val makes a reference unchangeable, which means you cannot assign a value to a val once it has been initialized. Immutable collections make the collection itself unchangeable not the reference to it. Each time you modify an immutable collection, another collection is produced instead of modifying the original collection in-place. Most collections have both immutable and mutable versions, but there are exceptions of course.

Comments

[Jus12]

In var a = 0, if two threads concurrently try to do a = 1 and a = 2 concurrently, how it is it handled? Does it not require locking?

[Dravidian]

"Each time you modify an immutable collection, another collection is produced instead of modifying the original collection in-place" - Is this true? Isn't it actually the responsibility of the programmer to deep clone the object and modify it? I thought it errors out when we try to modify an immutable collection.

[agilesteel]

There is no deep cloning. The references are "copied over" not the objects.