实施 TreeMap：为什么我不能打印自己定义的案例 class？

Question

我是 Scala 新手。

我正在尝试使用二叉搜索树实现 TreeMap。

我发现我可以打印一个非空的 TreeMap 但如果我尝试打印 Empty() （这是我定义的案例 class）

错误信息是：

[error] test.scala:33:16: type mismatch;

[error] found : Nothing <:< Nothing

[error] required: K => Ordered[K]

[error] println(Empty())

[error] ^

[error] one error found

[error] (test:compileIncremental) Compilation failed

我的源代码：

val tm:TreeMap[Int, String] = Node(Empty(), Empty(), 4, "ddd")
println(tm) // prints "4->ddd"
//println(Empty()) //This won't compile


abstract class TreeMap[K <% Ordered[K], +V] extends AbstractMap[K, V] {

//Implementation omitted.
    override def +[V1 >: V](key: (K, V1)): TreeMap[K, V1] = ......

    override def -(key: K): TreeMap[K, V] = ......

    override def get(key: K): Option[V] = ......

    override def iterator: Iterator[(K, V)] = ......
}

case class Empty[K <% Ordered[K]]() extends TreeMap[K, Nothing]
case class Node[K <% Ordered[K], +V](left: TreeMap[K, V], 
     right: TreeMap[K, V], key: K, value: V) extends TreeMap[K, V]

Answer 1

问题是您添加了一个类型参数和一个绑定到 Empty 的视图，但是您没有在第

行提供兼容的类型（也无法推断）

println(Empty())

可以在上一行推断出兼容类型：

 Node(Empty(), Empty(), 4, "ddd")

我认为正确的解决方法是将 Empty() 的密钥类型固定为 Nothing 并使 TreeMap 在密钥类型中协变，即

abstract class TreeMap[+K <% Ordered[K], +V] ...

case class Empty() extends TreeMap[Nothing, Nothing]

您还可以将 Empty 设为 case 对象，而不是 class，因为它是常量：

case object Empty extends TreeMap[Nothing, Nothing]

Answer 2

有意思。

很明显，Empty() 调用的类型解析存在问题。正如您可能知道的那样，[A <% Ordered[A]] 等同于 [A](implicit ev: A => Ordered[A])（顺便说一句，不推荐使用视图绑定）。所以我重写了你的方法有点不同（部分实现了缺失的方法）：

import scala.collection.AbstractMap

abstract class TreeMap[K, +V](implicit ev: K => Ordered[K])
  extends AbstractMap[K, V] {
  //Implementation omitted.
  override def +[V1 >: V](key: (K, V1)): TreeMap[K, V1] = this
  override def -(key: K): TreeMap[K, V] = this
  override def get(key: K): Option[V]
  override def iterator: Iterator[(K, V)]
}


case class Node[K, +V](left: TreeMap[K, V],
                       right: TreeMap[K, V],
                       key: K,
                       value: V)(implicit ev: K => Ordered[K]) 
  extends TreeMap[K, V] {
  override def get(key: K): Option[V] =
    if (key == this.key) Some(value)
    else None

  override def iterator: Iterator[(K, V)] =
    Iterator((key, value))
}

case class Empty[K](implicit ev: K => Ordered[K])
  extends TreeMap[K, Nothing] {
  override def get(key: K): Option[Nothing] = None
  override def iterator: Iterator[(K, Nothing)] = Iterator.empty
}

val tm: TreeMap[Int, String] =
  Node(Empty(), Empty(), 4, "ddd")
val tm2: TreeMap[Int, String] = Empty()

println(tm) // prints Map("4->ddd")
println(tm2) // prints Map()
println(Empty[Nothing]()) //prints Map()
//println(Empty()) //This won't compile

如您所见，即使调用 Empty[Nothing]() 也能正常工作。我希望 Empty() 应该以类似的方式工作，但不是。为了理解原因，我使用 scalac 选项 -Xprint:typer -Ydebug -Xprint-types -Ytyper-debug 来查看代码的差异：

object SomeClass extends App {
  case class Something3[T](implicit ev: T => Ordered[T])

  Something3()
}

和

object SomeClass extends App {
  case class Something3[T](implicit ev: T => Ordered[T])

  Something3[Nothing]()
}

看起来像编译器在解析类型时首先尝试解析隐式参数（它是 T => Ordered[T] 而不是 Nothing => Ordered[Nothing] 并得到 Nothing => Nothing），而不是类型 T，之后你会看到错误（这是我对比较输出的理解，没有深入了解编译器术语）。

我检查了 scala.collections.immutable.TreeMap 的实现，他们在后台使用委托实现了它。

据我所知，如果您想使用 AbstractMap 作为父级，则无法避免对 Empty 使用 Key 类型。 K 的变化方差也是不可能的。我想只要它是 compile-time 错误，你就可以保持原样（如果它是你实现中的唯一问题），并在注释中注释 stand-alone Empty 应该是显式键入 Key class（有意义的 class 或 Nothing）。

实施 TreeMap：为什么我不能打印自己定义的案例 class？

Implement TreeMap: why can't I print my own defined case class?

scala

treemap

case-class