IndexedSeq[Int] vs Array[Int]

Question

Coming from a Java background I am learning Scala and the following has me very confused. Why is the type returned different in these two (very similar but different) constructs, which vary only in how the source collection was build -

  val seq1: IndexedSeq[Int] = for (i <- 1 to 10) yield i

vs.

  val seq2: Array[Int] = for (i <- Array(1, 2, 3)) yield i

Please do point to me the right literature so that I can understand the core fundamentals at play here.

Answer 1

There are, in general, two different styles of collection operation libraries:

• type-preserving: that is what you are confused about in your question
• generic (not in the "parametric polymorphism sense" but the standard English sense of the word) or maybe "homogeneous"

Type-preserving collection operations try to preserve the type exactly for operations like filter, take, drop, etc. that only take existing elements unmodified. For operations like map, it tries to find the closest super type that can still hold the result. E.g. mapping over an IntSet with a function from Int to String can obviously not result in an IntSet, but only in a Set. Mapping an IntSet to Boolean could be represented in a BitSet, but I know of no collections framework that is clever enough to actually do that.

Generic / homogeneous collection operations always return the same type. Usually, this type is chosen to be very general, to accommodate the widest range of use cases. For example, In .NET, collection operations return IEnumerable, in Java, they return Streams, in C++, they return iterators, in Ruby, they return arrays.

Until recently, it was only possible to implement type-preserving collection operations by duplicating all operations for all types. For example, the Smalltalk collections framework is type-preserving, and it does this by having every single collections class re-implement every single collections operation. This results in a lot of duplicated code and is a maintenance nightmare. (It is no coincidence that many new object-oriented abstractions that get invented have their first paper written about how it can be applied to the Smalltalk collections framework. See Traits: Composable Units of Behaviour for an example.)

To my knowledge, the Scala 2.8 re-design of the collections framework (see also this answer on SO) was the first time someone managed to create type-preserving collections operations while minimizing (though not eliminating) duplication. However, the Scala 2.8 collections framework was widely criticized as being overly complex, and it has required constant work over the last decade. In fact, it actually lead to a complete re-design of the Scala documentation system as well, just to be able to hide the very complex type signatures that the type-preserving operations require. But, this still wasn't enough, so the collections framework was completely thrown out and re-designed yet again in Scala 2.13. (And this re-design took several years.)

So, the simple answer to your question is this: Scala tries as much as possible to preserve the type of the collection.

In your second case, the type of the collection is Array, and when you map over an Array, you get back an Array.

In your first case, the type of the collection is Range. Now, a Range doesn't actually have elements, though. It only has a beginning and an end and a step, and it produces the elements on demand while you are iterating over it. So, it is not that easy to produce a new Range with the new elements. The map function would basically need to be able to "reverse engineer" your mapping function to figure out what the new beginning and end and step should be. (Which is equivalent to solving the Halting Problem, or in other words impossible.) And what if you do something like this:

val seq1: IndexedSeq[Int] = for (i <- 1 to 10) yield scala.util.Random.nextInt(i)

Here, there isn't even a well-defined step, so it is actually impossible to build a Range that does this.

So, clearly, mapping over a Range cannot return a Range. So, it does the next best thing: It returns the most precise super type of Range that can contain the mapped values. In this case, that happens to be IndexedSeq.

There is a wrinkle, in that type-preserving collections operations challenge what we consider to be part of the contract of certain operations. For example, most people would argue that the cardinality of a collection should be invariant under map, in other words, map should map each element to exactly one new element and thus map should never change the size of the collection. But, what about this code:

Set(1, 2, 3).map { _ % 2 == 0 }
//=> Set(true, false)

Here, you get back a collection with fewer elements from a map, which is only supposed to transform elements, not remove them. But, since we decided we want type-preserving collections, and a Set cannot have duplicate values, the two false values are actually the same value, so there is only one of them in the set.

[It could be argued that this actually only demonstrates that Sets aren't collections and shouldn't be treated as collections. Sets are predicates ("Is this element a member?") rather than collections ("Give me all your elements!")]

Answer 2

this happens because construction:

for (x <-someSeq) yield x

is the same as:

someSeq.map(x => x)

for () yield is just syntactic sugar for flatMap/map function.

As we know map function doesn't change type of object-container, it changes elements inside container. So, in your example 1 to 10 has a type Range.Inclusive which extends Range, and Range extends IndexedSeq. Mapped IndexedSeq has the same type IndexedSeq.

for (i <- 1 to 10) yield i the same as (1 to 10).map(x => x)

In second case: for (i <- Array(1, 2, 3)) yield i you have an Array, and mapped Array type also Array.

for (i <- Array(1, 2, 3)) yield i the same as Array(1, 2, 3).map(x => x)

Answer 3

I think the right literature would be Scala for the Impatient by Cay Horstmann. The first edition is a little outdated but it's held up pretty well. The book is a fairly easy read almost to the end (I admit I don't quite understand lexical parsers or actors, but that's probably on me not Horstmann).

One of the things that Horstmann's book explains early on is that although you can use for like in Java, it can actually do much more sophisticated things. As a toy example, consider this Java procedure:

    public static void main(String[] args) {
        HashSet<Integer> squaresMod10 = new HashSet<>();
        for (int i = 1; i < 11; i++) {
            squaresMod10.add(i * i % 10);
        }
        for (Integer j : squaresMod10) {
            System.out.print(j + " ");
        }
    }

If you're using Java 8 or later, your IDE's probably advising you that you "can use functional operators." NetBeans rewrote it thus for me:

        squaresMod10.forEach((j) -> {
            System.out.print(j + " ");
        });

In Scala, you can use "functional operations" for both the i and j loops in this example. Rather than fire up IntelliJ just for this, I'll use the local Scala REPL on my system.

scala> (1 to 10).map(i => i * i % 10)
res2: IndexedSeq[Int] = Vector(1, 4, 9, 6, 5, 6, 9, 4, 1, 0)

scala> (1 to 10).map(i => i * i % 10).toSet
res3: scala.collection.immutable.Set[Int] = HashSet(0, 5, 1, 6, 9, 4)

scala> for (j <- res3) System.out.print(j + " ")
                                          ^
       warning: method + in class Int is deprecated (since 2.13.0): 
Adding a number and a String is deprecated. Use the string interpolation `s"$num$str"`
0 5 1 6 9 4

In Java, what would you be going for with seq1 and seq2? With a standard for loop in Java, you're essentially guiding the computer through the process of looking at each element of an ad hoc collection one by one and performing a certain operation on it.

Lambdas like the one NetBeans wrote for me still become If and Goto constructs at the JVM level, just like regular for loops in Java, as do a lot of what Horstmann calls "for comprehensions" in Scala. Either way, you're delegating the nuts and bolts of how exactly that happens to the compiler. In other words, you're not micro-managing.

However, as your seq2 example shows, it's still possible to wrap collections unnecessarily.

scala> 1 to 10
res5: scala.collection.immutable.Range.Inclusive = Range 1 to 10

scala> res5 == seq1
res6: Boolean = true

scala> Array(1, 2, 3)
res7: Array[Int] = Array(1, 2, 3)

scala> res7 == seq2
res8: Boolean = false

Okay, that didn't quite go the way I thought it would, but my point stands: in this vacuum, it's unnecessary to wrap 1 to 10 into another IndexedSeq[Int] and it's unnecessary to wrap an Array[Int] into another Array[Int]. Your for "statements" are merely wrapping unnamed collections into named collections.