Scala for-comprehension type inference

Question

The next code

  def f(chars: List[Char]): List[List[Char]] = chars match {
    case Nil => List(Nil)
    case x :: xs => for {
      v <- f(xs)
    } yield List(x) :: v
  }

gives the error message

- type mismatch;  found   : List[List[Any]]  required: List[List[Char]]

Please help me understand why 'for' chooses the most general Any instead of Char here? What topic in language spec should I read? Thanks.

Answer 1

The result, you are yielding is a mix of List[List[List[Char]]] and List[List[Char]]. Scala upcasts that to List[List[Any]]. For your case either of the following will do the job:

scala>  def f(chars: List[Char]): List[List[Char]] = chars match {
     |     case Nil => List(Nil)
     |     case x :: xs => for {
     |       v <- f(xs)
     |     } yield x :: v
     |   }
f: (chars: List[Char])List[List[Char]]

scala>  def f(chars: List[Char]): List[List[Char]] = chars match {
     |     case Nil => List(Nil)
     |     case x :: xs => for {
     |       v <- f(xs)
     |     } yield List(x) ++ v
     |   }
f: (chars: List[Char])List[List[Char]]

Answer 2

The problem is List(x) -- it needs to be x.

First, v iterates over the results of f(xs), and f returns List[List[Char]]. That means the result will be List[X], where X is the type returned by yield.

The type of v is List[Char], since it is iterating over the contents of f(xs). So we have to figure out the type of List(x) :: v, which is prepending a List[Char] on a List[Char]. It is not concatenating them: it is adding a list to a list containing only characters. The resulting list will have both Char and List[Char] in it.

Since the only type that satisfy both is Any, then X will be Any and the result of the for-comprehension List[Any].