1 :: List [nothing] in foldLeft

Question

If a:

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 will not work:

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

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

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

?

Although this happens in Haskell, for example:

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

Answer 1

Look at the scala foldLeft signature:

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

and haskell signature:

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

They are almost the same, but:

1) scala has a problem with the type of output between the [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 only select a larger type from left to right.

Moreover, this is a problem only for [pseudo] curry 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 chose a larger type - he found a common supertype of both T Thus, he tries to select a larger type (if it is on the left side) by default, but searches for a common supertype inside the same parameter list.

Note: I am talking about [pseudo] currying, since a method with several parameter lists (B)((B, A) => B)B becomes a card function only after the eta extension: foldLeft _ gives B => (B,A) => B

2) haskell uses the "object" of the List itself as a function parameter, which even allows you to:

  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, foldLeft and put monoid 'add' and 'identity' in the same parameter list (to avoid separate output from p.1):

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

and define the add polymorphic 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 comparison 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 cannot derive a generic type for lambda, so you cannot:

 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) 

since you cannot:

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

2 and 3) Since scala does not have any polymorphic lambda . It is impossible to deduce 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 extension of the famous add 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 subtype of any other type, in this case Int . Since List() is of type List[Nothing] , f is expected (List[Nothing], A) => List[Nothing]

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

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

When do you really:

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

And therefore, a type mismatch, because List[Int] cannot be List[Nothing] .

It looks like:

 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) ^