实现树状图：为什么我不能打印自己定义的案例类？

Question

我是Scala的新手。

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

我发现我可以打印一个非空TreeMap但代码无法编译，如果 我尝试打印Empty()(这是我定义的案例类)

错误消息是：

[错误] test.scala：33：16：类型不匹配;

[错误] 找到：没有<：<什么都没有>

[错误] 必需：K => 已订购[K]

[错误] println(Empty())

[错误] ^

[错误] 发现一个错误

[错误] (测试：编译增量) 编译失败

我的源代码：

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()调用的类型解析存在问题。您可能知道，[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的更改方差也是不可能的。我想一旦出现编译时错误，您就可以保持原样(如果它是实现中的唯一问题)，并在注释中注明应为Key类显式键入独立Empty(具有有意义的类或Nothing)。

Answer 2

问题是您添加了类型参数和绑定到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 object Empty extends TreeMap[Nothing, Nothing]