1 :: List[Nothing] in foldLeft

Question

If:

scala> val l = List()      // List() same as List[Nothing]()
l: List[Nothing] = List()

scala> 1 :: l
res0: List[Int] = List(1)

or:

scala> 1 :: List[Nothing]()
res6: List[Int] = List(1)

Why then this does not work out:

scala> List(1,2,3). foldLeft( List() ) ((acc,x) => x :: acc)

So I have to type this explicitly List[Int]():

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

?

Though it does in Haskell, for example:

 foldl (\acc x -> x:acc) [] [1,2,3]

Answer 1

Let's look at scala's foldLeft signature:

List[+A].foldLeft[B](z: B)(f: (B, A) ⇒ B): B

and haskell's signature:

foldl :: (b -> a -> b) -> b -> [a] -> b

They pretty much same, but:

1) scala has problem with type inference between [pseudo-]curried parameter lists, just compare:

 scala> def aaa[A](a: A)(b: A) = {}
 aaa: [A](a: A)(b: A)Unit

 scala> aaa(null: Any)(5)

 scala> aaa(5)(null: Any)
 <console>:21: error: type mismatch;
  found   : Any
  required: Int
              aaa(5)(null: Any)
                         ^

So scala can choose bigger type from left to right only.

More than that, this is a problem only for [pseudo-]curried functions:

scala> def aaa[T](a: T, b: T) = a
aaa: [T](a: T, b: T)T

scala> aaa(List("a"), List(6.0))
res26: List[Any] = List(a)

scala> aaa(List(6.0), List("a"))
res27: List[Any] = List(6.0)

Here scala not only picked a bigger type - it found a common supertype of both T's. So, it's trying to choose bigger type (if it's in the left part) by default, but looking for a common supertype inside one parameter list.

Note: I'm talking about [pseudo-] currying, as method with multiple parameter lists (B)((B, A) => B)B becoming curried function only after eta-expansion: foldLeft _ gives B => (B,A) => B

2) haskell uses "object" of List itself as function's parameter, which allows you to do even:

 Prelude> let f = foldl (\acc x -> x:acc) [] 
 :: [a] -> [a] //here is the polymorphic function
 Prelude> f [1,2,3]
 [3,2,1]
 Prelude> f ["1","2","3"]
 ["3","2","1"]

In scala you need:

 scala> def f[T](x: List[T]) = x.foldLeft(List[T]()) ((acc,x) => x :: acc)
 f: [T](x: List[T])List[T]

 scala> f(List(1,2,3))
 res3: List[Int] = List(3, 2, 1)

 scala> f(List("1","2","3"))
 res3: List[String] = List(3, 2, 1)

3) Finally, let's rewrite foldLeft and place monoid's 'add' and 'identity' to the same parameter list (to avoid separate inference from p.1):

 def foldLeft[T, U](l: List[T])(identity: U, add: (U,T) => U) = l.foldLeft(identity)(add)

and define polymorphic add operation:

 scala> def add[A](x: List[A], y: A) = y :: x
 add: [A](x: List[A], y: A)List[A]

So you can:

scala> foldLeft(List(1,2,3))(Nil, add)
res63: List[Int] = List(3, 2, 1)

in comparision with:

scala> List(1,2,3).foldLeft(Nil)(add)
 <console>:9: error: polymorphic expression cannot be instantiated to expected type;
  found   : [A, B](x: List[A], y: A)List[A]
  required: (scala.collection.immutable.Nil.type, Int) => scala.collection.immutable.Nil.type
          List(1,2,3).foldLeft(Nil)(add)
                                    ^

Unfortunately, scala can't infer generic type for lambdas, so you can't:

scala> foldLeft(List(1,2,3))(Nil, (acc,x) => x :: acc)
<console>:10: error: missing parameter type
          foldLeft(List(1,2,3))(Nil, (acc,x) => x :: acc)

as you can't:

scala> val a = (acc,x) => x :: acc
<console>:7: error: missing parameter type
   val a = (acc,x) => x :: acc
            ^

2 & 3) Because scala has no polymorphic lambdas at all. Can't infer A => List[A] => A (where A is a type parameter) from (acc,x) => x :: acc (even A => A from val a = (a) => a), but Haskell can:

Prelude> let lambda = \acc x -> x:acc
:: [a] -> a -> [a]
Prelude> let f = foldl(lambda) []
Prelude> f [1,2,3]
[3,2,1]

Here is an eta-expansion of perviously defined add generic method in scala:

scala> add _
res2: (List[Nothing], Nothing) => List[Nothing] = <function2>

Answer 2

def foldLeft[B](z: B)(f: (B, A) => B): B

Nothing is a sub-type of every other type, in this case Int. Since List() is inferred to have type List[Nothing], then f is expected to be (List[Nothing], A) => List[Nothing]

But in the function (acc, x) => x :: acc) , A is an Int, which means you should have:

(List[Nothing], Int) => List[Nothing]

When really you have:

(List[Nothing], Int) => List[Int]

And thus the type mismatch, because List[Int] can't be a List[Nothing].

This is similar to:

class A
class B extends A

scala> List.fill(5)(new A).foldLeft(List.empty[B])((acc, x) => x :: acc)
<console>:10: error: type mismatch;
 found   : A
 required: B
          List.fill(5)(new A).foldLeft(List.empty[B])((acc, x) => x :: acc)
                                                                    ^