Why is Scala's type inferencer not able to resolve this?

Question

In the code snippet below - why do I have to give a type annotation for Nil?

Welcome to Scala version 2.8.0.RC2 (OpenJDK Server VM, Java 1.6.0_18).
Type in expressions to have them evaluated.
Type :help for more information.

scala> List(Some(1), Some(2), Some(3), None).foldLeft(Nil)((lst, o) => o match { case Some(i) => i::lst; case None => lst })          
<console>:6: error: type mismatch;
found   : List[Int]
required: object Nil
   List(Some(1), Some(2), Some(3), None).foldLeft(Nil)((lst, o) => o match { case Some(i) => i::lst; case None => lst })
                                                                                              ^

scala> List(Some(1), Some(2), Some(3), None).foldLeft(Nil:List[Int])((lst, o) => o match { case Some(i) => i::lst; case None => lst })
res1: List[Int] = List(3, 2, 1)

Answer 1

The problem is that Nil is an object that extends List. That means that Nil.type is a subclass of List and, therefore, the type for foldLeft's accumulator will be Nil.type.

This is one place I wish Scala tried a bit (or a lot, whatever it takes :) harder to get a better type inferred.

Answer 2

You can avoid the trouble by doing it like this

private def removeNone[A](xs:List[Option[A]]) = {
    xs.filter(_.isInstanceOf[Some[_]]).map(_ match {
        case Some(t) => t
        case _ => ().asInstanceOf[A] //can't happen, needed to avoid warning
    })
}

While that might not directly answer your question, I wrote this function a couple hours ago and thought it couldn't hurt sharing it. You can leave out the 2nd case if you don't mind getting a warning.

I also find the combination of map and filter easier to read than fold. I try to use fold only where necessary.