Scala immutable operations on mutable collections

Question

AFAIK the Scala collection operations that are applied to immutable collections return a new collection which shares much of the structure of the former due to structural sharing.

My question is: considering that these operations can also be applied to mutable data structures returning a new structure, is the structural sharing in place as for immutable collections?

Answer 1

No, structural sharing is only possible when the part being shared is guaranteed to never change. Take immutable list for example: the reason it is safe for prepend to return a list that shares everything except the first element with the original one, is that the original one will never change. If this guarantee was not in place the prepend method would have to copy the entire list so that changes to the original would not effect the new list. For mutable collections this guarantee is not provided (since the original collection can in fact change), and therefore mutable collections can not make use of structural sharing.

Answer 2

No, since such sharing would violate either of the two: returning a new object with modified contents and not modifying the original collection when the new object is modified. Sharing structure only works well with immutable collections since immutability eliminates the risk of changing one object when the other one changes.

Of course there is sharing at the level of contents, e.g. in a mutable.List[String], the new list uses references to the same String instances as the original, but that's where it ends.