Using Nil as Initial Accumulator in Tail Recursive Function

Question

Mr. Daniel Sobral answered here that Nil can't be used as an initial accumulator to a fold.

Doesn't work with Nil as initial accumulator value

scala> xs
res9: List[Int] = List(1, 2, 3)

scala> xs.foldLeft(Nil)( (acc, elem) => elem.toString :: acc)
<console>:9: error: type mismatch;
 found   : List[String]
 required: scala.collection.immutable.Nil.type
              xs.foldLeft(Nil)( (acc, elem) => elem.toString :: acc)

But it will work if I pass List[String]().

scala> xs.foldLeft(List[String]())( (acc, elem) => elem.toString :: acc)
res7: List[String] = List(3, 2, 1)

Yet why can I use Nil in the following tail recursive function?

scala>       def toStringList(as: List[Int]): List[String] = {
     |         def go(bs: List[Int], acc: List[String]): List[String]= bs match {
     |           case Nil => acc
     |           case x :: xs => go(xs, x.toString :: acc)
     |         }
     |        println(as)
     |        go(as, Nil)   
     |       }
toStringList: (as: List[Int])List[String]

Answer 1

The problem is that Scala starts type inference with the first parameter list. So given def foldLeft[B](z: B)(f: (B, A) => B): B and

xs.foldLeft(Nil)(...)

it infers B as Nil.type (type which has only one value: Nil) and uses this to type-check the second parameter list, which obviously fails. However, List[String]() has the type List[String] and so B is List[String], which will work with your f. Another workaround is to write the type parameter explicitly:

xs.foldLeft[List[String]](Nil)(...)

In the second program, type of acc is given (and has to be, since it's a function argument), so no type inference happens corresponding to your initial problem.