Composing Option with List in for-comprehension gives type mismatch depending on order

Question

Why does this construction cause a Type Mismatch error in Scala?

for (first <- Some(1); second <- List(1,2,3)) yield (first,second)

<console>:6: error: type mismatch;
 found   : List[(Int, Int)]
 required: Option[?]
       for (first <- Some(1); second <- List(1,2,3)) yield (first,second)

If I switch the Some with the List it compiles fine:

for (first <- List(1,2,3); second <- Some(1)) yield (first,second)
res41: List[(Int, Int)] = List((1,1), (2,1), (3,1))

This also works fine:

for (first <- Some(1); second <- Some(2)) yield (first,second)

Answer 1

For comprehensions are converted into calls to the map or flatMap method. For example this one:

for(x <- List(1) ; y <- List(1,2,3)) yield (x,y)

becomes that:

List(1).flatMap(x => List(1,2,3).map(y => (x,y)))

Therefore, the first loop value (in this case, List(1)) will receive the flatMap method call. Since flatMap on a List returns another List, the result of the for comprehension will of course be a List. (This was new to me: For comprehensions don't always result in streams, not even necessarily in Seqs.)

Now, take a look at how flatMap is declared in Option:

def flatMap [B] (f: (A) ⇒ Option[B]) : Option[B]

Keep this in mind. Let's see how the erroneous for comprehension (the one with Some(1)) gets converted to a sequence of map calls:

Some(1).flatMap(x => List(1,2,3).map(y => (x, y)))

Now, it's easy to see that the parameter of the flatMap call is something that returns a List, but not an Option, as required.

In order to fix the thing, you can do the following:

for(x <- Some(1).toSeq ; y <- List(1,2,3)) yield (x, y)

That compiles just fine. It is worth noting that Option is not a subtype of Seq, as is often assumed.

Answer 2

An easy tip to remember, for comprehensions will try to return the type of the collection of the first generator, Option[Int] in this case. So, if you start with Some(1) you should expect a result of Option[T].

If you want a result of List type, you should start with a List generator.

Why have this restriction and not assume you'll always want some sort of sequence? You can have a situation where it makes sense to return Option. Maybe you have an Option[Int] that you want to combine with something to get a Option[List[Int]], say with the following function: (i:Int) => if (i > 0) List.range(0, i) else None; you could then write this and get None when things don't "make sense":

val f = (i:Int) => if (i > 0) Some(List.range(0, i)) else None
for (i <- Some(5); j <- f(i)) yield j
// returns: Option[List[Int]] = Some(List(0, 1, 2, 3, 4))
for (i <- None; j <- f(i)) yield j
// returns: Option[List[Int]] = None
for (i <- Some(-3); j <- f(i)) yield j
// returns:  Option[List[Int]] = None

How for comprehensions are expanded in the general case are in fact a fairly general mechanism to combine an object of type M[T] with a function (T) => M[U] to get an object of type M[U]. In your example, M can be Option or List. In general it has to be the same type M. So you can't combine Option with List. For examples of other things that can be M, look at subclasses of this trait.

Why did combining List[T] with (T) => Option[T] work though when you started with the List? In this case the library use a more general type where it makes sense. So you can combine List with Traversable and there is an implicit conversion from Option to Traversable.

The bottom line is this: think about what type you want the expression to return and start with that type as the first generator. Wrap it in that type if necessary.

Answer 3

It probably has something to do with Option not being an Iterable. The implicit Option.option2Iterable will handle the case where compiler is expecting second to be an Iterable. I expect that the compiler magic is different depending on the type of the loop variable.

Answer 4

I always found this helpful:

scala> val foo: Option[Seq[Int]] = Some(Seq(1, 2, 3, 4, 5))
foo: Option[Seq[Int]] = Some(List(1, 2, 3, 4, 5))

scala> foo.flatten
<console>:13: error: Cannot prove that Seq[Int] <:< Option[B].
   foo.flatten
       ^

scala> val bar: Seq[Seq[Int]] = Seq(Seq(1, 2, 3, 4, 5))
bar: Seq[Seq[Int]] = List(List(1, 2, 3, 4, 5))

scala> bar.flatten
res1: Seq[Int] = List(1, 2, 3, 4, 5)

scala> foo.toSeq.flatten
res2: Seq[Int] = List(1, 2, 3, 4, 5)