Why doesn't passing Nil to foldLeft work?

Question

When I build a list using foldLeft I often get annoyed at having to explicitly type the injected parameter and wish I could just use `Nil' instead - here's a contrived example:

scala> List(1,2,3).foldLeft(List[Int]())((x,y) =>  y :: x)
res17: List[Int] = List(3, 2, 1)

scala> List(1,2,3).foldLeft(Nil)((x, y) => y :: x)
<console>:10: error: type mismatch;
 found   : List[Int]
 required: scala.collection.immutable.Nil.type
              List(1,2,3).foldLeft(Nil)((x,y) =>  y :: x)

This isn't so bad with a List[Int] but as soon as you start using lists of your own classes, which are almost certainly going to have longer names, or even lists of tuples or other containers, so there are multiple class names you need to specify, it gets horrendous:

list.foldLeft(List.empty[(SomethingClass, SomethingElseClass)]) { (x,y) => y :: x }

I'm guessing that the reason it doesn't work is that whereas with something like 5 :: Nil the compiler can infer the type of the empty list to be List[Int], but when Nil is passed as a parameter to foldLeft it doesn't have enough information to do so, and by the time it gets round to being used its type is set. But - is it really true that it couldn't? Could it not infer the type from the return type of the function passed as the second argument?

And if not, is there some neater idiom I just don't know about?

Answer 1

Scalas type inference engine works from left to right - therefore scalac can not infer the correct type for the first parameter list of foldLeft. You have to give the compiler a hint what type to use. Instead of using List[TYPE]() you can use List.empty[TYPE]:

(List(1,2,3) foldLeft List.empty[Int]) { (x,y) =>  y :: x }
(List.empty[Int] /: List(1, 2, 3)) { (x,y) => y :: x }

Answer 2

Scala's type inference works one parameter block at a time. Nil without any other context has no particular type, so the most restrictive type possible (Nothing) is chosen.

It also can't infer the return type of the function because the return type depends on the type of Nil. Getting out of that sort of circularity is tricky in general (if you don't specify what you mean).

There are a few tricks that you can apply, though, to make things less cumbersome.

First, the type signature of fold has only the type of the collection, so if you can use that sort of fold, you can get around the problem. For example, you could write your own reverse-flatten:

List(List(1),List(2),List(3)).fold(Nil)( (x,y) => y ::: x )

Second, if you're creating a new collection of the same type, it's often easier to use the existing collection to generate an empty one than to try to plug the types in for an empty collection. It's especially easy if you have pipe defined somewhere:

class PipeAnything[A](a: A) { def |>[B](f: A => B) = f(a) }
implicit def anything_can_be_piped[A](a: A) = new PipeAnything(a)

List(1,2,3) |> { x => x.foldLeft(x.take(0))( (y,z) => z :: y ) }

Finally, don't forget that you can define your own methods pretty easily that can do something consistent with your types, even if you have to use a bit of trickery to get it to work:

def foldMe[A,B](example: A, list: List[B])(f: (List[A],B) => List[A]) = {
  (List(example).take(0) /: list)(f)
}

scala> foldMe( ("",0), List("fish","wish","dish") )( (x,y) => (y.take(1), y.length) :: x )
res40: List[(java.lang.String, Int)] = List((d,4), (w,4), (f,4))

Here, note that the example is not a zero, but rather is only used as an exemplar of the thing with the type that you want.