Type inference: Using generic methods with implicit type conversion

Question

The problem is that you want to flatMap a List[Option[T]] to a List[T] :

val l = List(Some("Hello"), None, Some("World"))

to get:

List(Hello, World)

but there is no nice solution:

l flatMap( o => o)
l flatMap identity[Option[String]]
l flatMap ( x => Option.option2Iterable(identity(x)))
for(x <- l; y <- x) yield y

The obvious solution using the identity function does not work, due to a needed type conversion from Option[T] to Iterable[T]:

l flatMap identity

<console>:6: error: type mismatch;
 found   : A
 required: Iterable[?]
       l flatMap identity

Is there a way around this problem?

Part of the question is why does the type inferencer work differently if implicit type conversions are needed?

(This question came up when this question about the identity function was discussed.)

Answer 1

Make Option extend the Iterable trait; I wonder why they didn't do this in the first place...

Note that the example does not work in scala 2.8 with type hints either:

scala> val l = List(Some("Hello"), None, Some("World"))
l: List[Option[java.lang.String]] = List(Some(Hello), None, Some(World))

scala> l.flatMap(identity) : List[String]
<console>:6: error: type mismatch;
 found   : A
 required: Traversable[?]
   l.flatMap(identity) : List[String]

Answer 2

There is no problem with the implicit. If it were a list of list, you wouldn't be able to pass identity to map or flatMap either. Let's discuss map instead of flatMap, because it is simpler, so that I can better explain what I think is happening.

The type of identity is (A) => A. The type of map if (A) => B, where A is known, because it is the type parameter of the object (ie, in a List[String], it is String). Neither identity's A nor map's B is known.

Now, if we used the left side of map's type to infer the left side of identity, then we could use the right side of identity to infer the right side of map. See a cycle? map's type to identity's type to map's type again. I'm pretty sure the type inferencer avoids cycles, otherwise it could be stuck in an infinite loop.

In fact, one can look at page 355 of Odersky et al's Programming in Scala the details of the type inferencer. In a method application m(arg), it does the following steps:

1. It checks whether method m (map, in our case) has a known type (no, we don't know B).
2. It checks if the argument arg (identity in our case) has a known type (no, we don't know A).
3. It bails out.

So, you have to provide one type. For example:

l.flatMap[String](identity)
l.flatten[String]

On Scala 2.8 the type inferencer is a little bit cleverer, and can handle the second command without passing the type explicitly.