scala - Scala 如何确定 TreeSet 构造函数的隐式类型参数

Question

我正在做“Scala for the impatient”一书中的练习，偶然发现了这个魔法。我有一个用于执行代码的简单 Scala 对象:

object Main {

  def main(args: Array[String]): Unit = {
    println(charIndex("Missisipi"))
    //var s = scala.collection.immutable.SortedSet[Int]()
  }

  def charIndex(s: String) : scala.collection.mutable.Map[Char, scala.collection.mutable.TreeSet[Int]] = {
    val m = scala.collection.mutable.Map[Char, scala.collection.mutable.TreeSet[Int]]()
    s.zipWithIndex.foreach{
      case (c, i) => m += c -> (m.getOrElse(c, scala.collection.mutable.TreeSet()) += i)
    }
    m
  }
}

无论它看起来如何(我用最丑陋的方式做到了)，但在这种情况下它不会编译错误:

Error:(14, 80) diverging implicit expansion for type scala.math.Ordering[T1] starting with method Tuple9 in object Ordering case (c, i) => m += c -> (m.getOrElse(c, scala.collection.mutable.TreeSet()) += i) Error:(14, 80) not enough arguments for method apply: (implicit ord: scala.math.Ordering[A])scala.collection.mutable.TreeSet[A] in class SortedSetFactory. Unspecified value parameter ord. case (c, i) => m += c -> (m.getOrElse(c, scala.collection.mutable.TreeSet()) += i)

但是如果你在 main 方法中取消注释行，它将被成功编译。为什么会这样？

Answer 1

问题的核心

如果你用 -Xlog-implicits 运行这个例子(对于 sbt scalacOptions := Seq( "-Xlog-implicits"))你会看到很多 [info] 像这样的消息

math.this.Ordering.Tuple6 is not a valid implicit value for scala.math.Ordering[A] because: [info] diverging implicit expansion for type scala.math.Ordering[T1]

这基本上适用于 math.this.Ordering 中的所有类型，从简单的 Boolean 到 Iterables 和 Options。

它告诉我们当 getOrElse 失败时，编译器会疯狂地猜测您正在尝试构造什么类型的 TreeSet。在您的示例中，它只是一个 TreeSet 没有任何 [explicit] 类型，因此编译器必须找到一个隐式类型来绑定(bind)新的 TreeSet 。通过在 TreeSet 构造函数中指定 Int，您将消除对隐式的搜索，并且代码将没有任何魔法。

case ( c, i ) =>  m += c -> ( m.getOrElse( c, scala.collection.mutable.TreeSet[Int]() ) += i)

现在，进入重点。

编译器如何搜索隐式，也就是为什么这个魔法起作用了

您指定 m 是一个 Map 到 TreeSet[Int]，这很好，但是 .getOrElse 会当无法获取第一个字符时，返回 m 的默认值。要构造该默认值，它将使用您提供的定义

scala.collection.mutable.TreeSet()

在.getOrElse 的文档中我们可以see对于默认值，编译器将使用第二个参数计算产生的结果。 TreeSet 的构造函数 need知道你想在那个集合中保留什么类型的值，如果它没有看到明确的定义，它将寻找隐含的。

new TreeSet()(implicit ord: Ordering[A])

正如我在开始时提到的，它会暴力破解 Ordering 中所有可能的类型，因为，你知道，它必须是面向排序的类型，但棘手的部分是它不知道是什么类型它实际上需要。编译器必须构造一个新的 TreeSet 才能对其 += i 。它不能只是向前看，看到i是Int，构造一个TreeSet[Int]，然后返回添加i 给它。那将是一个真正的魔法。

有一个很棒的post关于 scala 如何确定隐式参数的类型。请注意，SortedSet 是通过 traits 连接的到 TreeSet 所以它不能归入类别“T 的某些部分”。在这种特殊情况下，编译器将看到一个显式定义的 SortedTree[Int]，并且由于没有其他选项，将使用 Int 作为 TreeSet 的隐式类型.