Why no immutable arrays in scala standard library?

Scala has all sorts sorts of immutable sequences like List, Vector,etc. I have been surprised to find no implementation of immutable indexed sequence backed by a simple array (Vector seems way too complicated for my needs).

• Is there a design reason for this? I could not find a good explanation on the mailing list.

• Do you have a recommendation for an immutable indexed sequence that has close to the same performances as an array? I am considering scalaz's Im开发者_JAVA百科mutableArray, but it has some issues with scala trunk for example.

Thank you

You could cast your array into a sequence.

val s: Seq[Int] = Array(1,2,3,4)

The array will be implicitly converted to a WrappedArray. And as the type is Seq, update operations will no longer be available.

So, let's first make a distinction between interface and class. The interface is an API design, while the class is the implementation of such API.

The interfaces in Scala have the same name and different package to distinguish with regards to immutability: Seq, immutable.Seq, mutable.Seq.

The classes, on the other hand, usually don't share a name. A List is an immutable sequence, while a ListBuffer is a mutable sequence. There are exceptions, like HashSet, but that's just a coincidence with regards to implementation.

Now, and Array is not part of Scala's collection, being a Java class, but its wrapper WrappedArray shows clearly where it would show up: as a mutable class.

The interface implemented by WrappedArray is IndexedSeq, which exists are both mutable and immutable traits.

The immutable.IndexedSeq has a few implementing classes, including the WrappedString. The general use class implementing it, however, is the Vector. That class occupies the same position an Array class would occupy in the mutable side.

Now, there's no more complexity in using a Vector than using an Array, so I don't know why you call it complicated.

Perhaps you think it does too much internally, in which case you'd be wrong. All well designed immutable classes are persistent, because using an immutable collection means creating new copies of it, so they have to be optimized for that, which is exactly what Vector does.

Mostly because there are no arrays whatsoever in Scala. What you're seeing is java's arrays pimped with a few methods that help them fit into the collection API.

Anything else wouldn't be an array, with it's unique property of not suffering type erasure, or the broken variance. It would just be another type with indexes and values. Scala does have that, it's called IndexedSeq, and if you need to pass it as an array to some 3rd party API then you can just use .toArray

Scala 2.13 has added ArraySeq, which is an immutable sequence backed by an array.

Scala 3 now has IArray, an Immutable Array.

It is implemented as an Opaque Type Alias, with no runtime overhead.

The point of the scala Array class is to provide a mechanism to access the abilities of Java arrays (but without Java's awful design decision of allowing arrays to be covariant within its type system). Java arrays are mutable, hence so are those in the scala standard library.

Suppose there were also another class immutable.Array in the library but that the compiler were also to use a Java array as the underlying structure (for efficiency/speed). The following code would then compile and run:

val i = immutable.Array("Hello")
i.asInstanceOf[Array[String]](0) = "Goodbye"
println( i(0) ) //I thought i was immutable :-(

That is, the array would really be mutable.

The problem with Arrays is that they have a fixed size. There is no operation to add an element to an array, or remove one from it.

You can keep an array that you guess will be long enough as a backing store, "wasting" the memory you're not using, keep track of the last used index, and copy to a larger array if you need the extra space. That copying is O(N) obviously.

Changing a single element is also O(N) as you will need to copy over the entire array. There is no structural sharing, which is the lynchpin of performant functional datastructures.

You could also allocate an extra array for the "overflowing" elements, and somehow keep track of your arrays. At that point you're on your way of re-inventing Vector.

In short, due to their unsuitablility for structural sharing, immutable facades for arrays have terrible runtime performance characteristics for most common operations like adding an element, removing an element, and changing an element.

That only leaves the use-case of a fixed size fixed content data-carrier, and that use-case is relatively rare. Most uses better served with List, Stream or Vector

You can simply use Array[T].toIndexSeq to convert Array[T] to ArraySeq[T], which is of type immutable.IndexedSeq[T]. (after Scala 2.13.0)

scala> val array = Array(0, 1, 2)
array: Array[Int] = Array(0, 1, 2)

scala> array.toIndexedSeq
res0: IndexedSeq[Int] = ArraySeq(0, 1, 2)