How Scala knows what collection implementation to use?

Question

val set1 = Set(1,2,3)

or

val list1 = List(1,2,3)

Can you describe a precise mechanics behind the construction of such objects?

In Java we need HashSet or LinkedList to construct the object.

Here we see traits used with apply method?

Where IS this apply method?

Something with implicits?

Answer 1

Traits can have companion objects. So when you call Set(1, 2, 3), you're actually calling the apply method on the companion object Set. For example, you can see the Set companion object documentation here, and its source code here.

Each collection type's companion object has a default implementation that is instantiated with use of apply. In fact, the collection type's companion objects all extend from the abstract class GenericCompanion, which encapsulates this behavior.

Here is an image of the Scala immutable collections type hierarchy. An arrow from A to B means B extends A, a dotted arrow means B is implicitly viewable as a A, and a bold line means that the apply method on the companion object of A returns an instance of B.

So, for example, when you call Iterable(1, 2, 3), you get a List, since there are bold lines from Iterable to Seq to LinearSeq to List. You can read more about the Scala collections type hierarchy (including the mutable versions) here.

When coming from Java, this may be surprising, but it actually makes a lot of sense. When you're instantiating an Set, for example, you might not care what the actual implementation is and in fact just want all the guarantees of the Set type contract, and can trust the language to pick an implementation.

You happened to use Set in your question, which is slightly more complicated. Sets with fewer than 5 elements have special implementations for efficiency. So the bold arrow in the above diagram shows only the usual case (for sufficiently large Sets). For example:

Set(1, 2, 3, 4, 5).asInstanceOf[HashSet[Int]] // Works as expected
Set(1, 2, 3).asInstanceOf[HashSet[Int]] // Doesn't work!
Set(1, 2, 3).asInstanceOf[collection.immutable.Set.Set3[Int]] // Set3 is the special implementation of sets with example 3 elements.

As a final note on working with collections, using the REPL here is really useful in figuring out the default implementations of the collection traits (without needing to refer to the diagram). For example, here we can see that the Iterable companion object constructs a List, as expected:

Iterable(1, 2, 3)
>>> Iterable[Int] = List(1, 2, 3)

Answer 2

List has a companion object which has the apply defined as:

override def apply[A](xs: A*): List[A] = xs.toList

More in depth

So, now we are left with the question of where does the xs varargs go? This essentially boils down to a TraversableOnce, which has its toList calling

  def to[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] = {
    val b = cbf()
    b ++= seq
    b.result()
  }

which leads to CanBuildFrom...which is not a simple answer - so I will simply point you in the right direction on that one