scala - 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

和 haskell 的签名:

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

它们几乎相同，但是:

1) scala 在 [pseudo-]curried 参数列表之间存在类型推断问题，只需比较:

 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只能从左到右选择更大的类型。

不仅如此，这只是 [pseudo-]curried 函数的问题:

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 的共同父类(super class)型。的。因此，它默认尝试选择更大的类型(如果它在左侧)，但在一个参数列表中寻找一个共同的父类(super class)型。

注意:我说的是 [pseudo-] 柯里化(Currying)，作为具有多个参数列表的方法 (B)((B, A) => B)B仅在 eta 扩展后成为柯里化(Currying)函数: foldLeft _给 B => (B,A) => B
2) haskell 使用 List 的“对象”本身作为函数的参数，它甚至可以让你做:

 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> 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并将 monoid 的 'add' 和 'identity' 放在同一个参数列表中(以避免从 p.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 有 没有多态 lambda 一点也不。无法推断 A => List[A] => A (其中 A 是类型参数)来自 (acc,x) => x :: acc (甚至 A => A 来自 val a = (a) => 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]

这是以前定义的 add 的 eta 扩展。 scala中的通用方法:

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