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

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(开发者_JAVA技巧2)) yield (first,second)

---

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.

---

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.

---

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.

---

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)

---

Since Scala 2.13 Option was made IterableOnce

sealed abstract class Option[+A] extends IterableOnce[A] with Product with Serializable

so the following for comprehension works without the use of option2Iterable implicit conversion

scala> for {
     |   a <- List(1)
     |   b <- Some(41)
     | } yield (a + b)
val res35: List[Int] = List(42)

scala> List(1).flatMap
final override def flatMap[B](f: Int => scala.collection.IterableOnce[B]): List[B]

where we see List#flatMap takes a function to IterableOnce. Desugaring above for comprehension we get something like

List(1).flatMap(a => Some(41).map(b => a + b))

which show the absence of the implicit conversion.

However in Scala 2.12 and before Option was not a traversable/iterable entity

sealed abstract class Option[+A] extends Product with Serializable 

so the above for comprehension would desugar to something like

List(1).flatMap(a => option2Iterable(Some(41)).map(b => a + b))(List.canBuildFrom[Int])

where we see the implicit conversion.

The reason it does not work the other way around where for comprehension begins with Option and then we try to chain a List

scala> for {
     |   a <- Option(1)
     |   b <- List(41)
     | } yield (a + b)
         b <- List(41)
           ^
On line 3: error: type mismatch;
        found   : List[Int]
        required: Option[?]

scala> Option(1).flatMap
final def flatMap[B](f: Int => Option[B]): Option[B]

is because Option#flatMap takes a function to Option and converting a List to Option probably does not make sense because we would lose elements for Lists with more than one element.

As szeiger explains

I think the recent Option changes actually make the for comprehensions use case easier to understand because you do not need an implicit conversion anymore. Option can be used on the RHS of a flatMap of any collection type because it is IterableOnce (but not the opposite because the RHS of Option#flatMap requires Option).