1 :：List[Nothing] in foldLeft

Question

如果：

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

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

或者：

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

为什么这样做没有结果呢：

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

所以我必须输入这个显式的List[Int]()

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

例如，在Haskell中是这样的：

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

Answer 1

让我们看一下scala的foldLeft签名：

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

哈斯克尔的签名：

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

它们大致相同，但是：

1) scala在伪参数列表之间的类型推断方面存在问题，只需比较：

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

因此scala只能从左到右选择更大的类型。

更重要的是，这只是伪咖喱函数的一个问题：

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)

这里，scala不仅选择了一个更大的类型--它找到了两个T的通用超级类型。因此，它试图在默认情况下选择更大的类型(如果在左边)，而是在一个参数列表中寻找一个公共的超级类型。

注意:我说的是伪跑，作为具有多参数列表的方法，(B)((B, A) => B)B只有在eta扩展之后才会成为临时函数：foldLeft _给出了B => (B,A) => B。

2) haskell使用List本身的"object“作为函数的参数，它允许您执行以下操作：

 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"]

在scala中，您需要：

 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)最后，让我们重写foldLeft，并将幺半群的'add‘和'identity’放在相同的参数列表中(以避免从第1页单独推断)：

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

并定义多态add操作：

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

所以你可以：

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

与以下方面相比较：

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

不幸的是，scala无法推断lambdas的泛型类型，所以您不能：

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)

因为你不能：

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

2& 3)因为scala有，所以根本没有多态lambdas。不能从A => List[A] => A (甚至A => A来自val a = (a) => a)推断出(acc,x) => x :: acc (其中A是类型参数)，但是Haskell可以：

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

下面是scala中明确定义的add泛型方法的eta扩展：

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

Answer 2

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

Nothing是所有其他类型的子类型，在本例中是Int。因为List()被推断为List[Nothing]类型，所以f被认为是(List[Nothing], A) => List[Nothing]

但是在函数(acc, x) => x :: acc)中，A是一个Int，这意味着您应该拥有：

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

当你真正拥有：

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

因此类型不匹配，因为List[Int]不能是List[Nothing]。

这类似于：

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