Scala 类型检查编译错误

Question

我有以下功能

  def map[A,B](l: List[A])(f: A => B): List[B]

  def concat[A](l: List[List[A]]): List[A]

我想实现这个

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B]

现在，我知道正确的解决方案是(所以这不是问题)

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = 
    concat(map(l)(f))

但是当我试图解决它时，我首先尝试使用(我忘记了连接)

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = 
    map(l)(f)

// compilation output
[error]  found   : A => fpinscala.datastructures.List[B]
[error]  required: A => B
[error]     map(l)(f)

我无法理解该错误，因为看起来 map(l)(f) 的计算是错误的，但事实并非如此，这是 flatMap 函数的返回值出了什么问题.

事实上，如果将相同的实现分解为两行代码，我们可以看到 Scala 编译器会提示另一个不同的错误 - 实际上是我在前面的代码中预期的错误。

  def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = {
    var result = map(l)(f)
    result
  }

// compilation output
[error]  found   : fpinscala.datastructures.List[fpinscala.datastructures.List[B]]
[error]  required: fpinscala.datastructures.List[B]
[error]     result

谁能解释一下为什么第一次尝试代码的编译会出现与第二次不同类型的错误？

Answer 1

你必须知道 Scala 如何检查类型。它正在使用 Unification algorithm 。简而言之，这意味着它遵循自上而下的方法。

回想一下 map 的类型为 List[U] => (U => V) => List[V] (无论 U] 类型如何 code> 和 V 是)。在第一个错误代码中，您写道您的函数返回一个 List[B]。因此，您告诉 Scala map(l)(f) 必须是 List[B] 类型。现在您以自上/下的方式传播包含。要使 map(l)(f) 成为 List[B] 类型，您需要拥有 List[ 类型的 l A](无论 A 是什么)和类型为 A => B 的 f。因此，编译器会提示，因为您给出了 A => list[B] 类型的 f。

如果第二个错误的代码，您已经正确计算出List[List[B]]类型的结果。但是，在第二行中，您尝试返回 result，但您的函数被声明为返回 list[B]。因此出现错误消息。