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

Question

I'm new to Scala.

I'm trying to implement TreeMap using Binary Search Tree.

I found that I can print a non-empty TreeMap but the code won't compile if I try to print Empty() (which is a case class defined by me)

The error message is:

[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

My source code:

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

Interesting.

It is clear, that problem in type resolution for Empty() call. As you probably know, [A <% Ordered[A]] is equivalent to [A](implicit ev: A => Ordered[A]) (and view bound is deprecated by the way). So I rewrote you approach a bit different (with partial implementation of missing methods):

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

As you can see even call Empty[Nothing]() works. I would expect that Empty() should work similar way, but no. To understand why, I used scalac options -Xprint:typer -Ydebug -Xprint-types -Ytyper-debug to see the difference for codes:

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

  Something3()
}

and

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

  Something3[Nothing]()
}

Looks like compiler while resolving type first try to resolve implicit parameter (which is T => Ordered[T] instead of Nothing => Ordered[Nothing] and got Nothing => Nothing), and than type T, and after that you see error (it is my understanding of what I see comparing output, without deep knowledge in compiler terms).

I checked implementation of scala.collections.immutable.TreeMap, and they implemented it with delegate under the hood.

As I can see that you cannot avoid using Key type for Empty, if you want to go with AbstractMap as parent. And change variance for K is not possible as well. I suppose that as soon as it is compile-time error, you can leave it as is (if it is the only problem in your implementation), with note in comment that stand-alone Empty should be explicitly typed for Key class (either with meaningful class or Nothing).