How does the Scala type checker know to prevent calling flatten on a List that is already flat

Question

I'm kind of new to Scala and I have a question about the type system.

The flatten method works on nested collections, so if I have a List of Lists it will flatten it into a List. But it does not make sense to call flatten on a collection that is already flat. And sure enough the Scala type checker will flag that as an error.

List(List(1,2,3),List(4,5,6)).flatten // produces List(1,2,3,4,5,6)
List(1,2,3,4).flatten  // type error

I understand that this somehow relies on an implicit parameter to flatten. But I don't know where the implicit value comes from and how it is used to assert the type of the object flatten is called on. Also, why doesn't the implicit parameter show up in the scaladocs for List.flatten?

Answer 1

To understand how this works, we need to have a look at the type signature of flatten:

def flatten[B](implicit asTraversable: (A) ⇒ GenTraversableOnce[B]): List[B]

A is the element type of the list and B is the type of the elements of each element. In order for flatten to work, there has to be an implicit conversion from the element types to a GenTraversableOnce[B]. That is only the case for collections or if you implement your own implicit conversion. For example, you could define one for pairs:

implicit def pairToList[A](p:(A,A)) = List(p._1, p._2)

List(1->2,2->3).flatten //compiles! List(1,2,2,3)

Answer 2

The trick is an implicit witness that ensures that the elements in the list are traversable. Here is the (slightly simplified) signature of flatten taken from GenericTraversableTemplate:

def flatten[B](implicit asTraversable: A => TraversableOnce[B])
              : GenTraversable[B] =

In your case, the witness cannot be found for elements of type Int, and the invocation of flatten is therefore rejected by the compiler.

If you wanted to make your example compile, you could use the following implicit definition:

implicit def singleToList[A](a: A) = List(a)

(As a side-note: I'd consider such an implicit as quite dangerous, since it's applicability is very general, which can result in unpleasant surprises because the compiler might inject invocations at various places without you being aware of it.)