找不到参数排序的隐式值

Question

尝试编译此错误时出现以下错误：

Btree.scala:9: 错误: 无法找到参数排序的隐式值: Ordering[K] 抽象类 Node[K,V] 扩展 TreeMap[K,V]

TreeMap 应该接受我提供的隐式 Ordering[A] val。也许隐式参数需要位于实例化 Btree(TreeMap) 的对象 Tester 中？ 我更愿意将隐式声明保留在 Btree 类中，因为我希望 Ordering 有一个实现 Comparable[K] 的类型 K。有道理吗？

package disttree {
    import scala.collection.immutable.TreeMap

    class Btree[K <: Comparable[K],V](fanout:Int) {
        implicit object DefaultOrder extends Ordering[K] {
            def compare(k1: K, k2: K) = k1 compareTo k2
        }

        abstract class Node[K,V] extends TreeMap[K,V]

        class InnerNode[K,V] extends Node[K,V]

        class LeafNode[K,V] extends Node[K,V]

        val root = new InnerNode[K,V]()

        def search(n: Node[K,V], key: K): Option[(K,V)] = {
            return n.find(_ == key)
        }

        def insert(key: K, value: V) { }

        def delete(key: K) { }
    }
}

import disttree._;
object Tester {
    def main(args: List[String]) = {
        var t = new Btree[Int, Any](2)
        t.insert(1, "goodbye")
        Console.println(t)
    }
}

Answer 1

常见错误。这是两个不同的 K：

class Btree[K <: Comparable[K],V](fanout:Int) {
    // The K below is the type parameter of Btree
    implicit object DefaultOrder extends Ordering[K] {
        def compare(k1: K, k2: K) = k1 compareTo k2
    }

    // The K in the error is the type parameter of Node
    abstract class Node[K,V] extends TreeMap[K,V]

    // And this is yet another K
    class InnerNode[K,V] extends Node[K,V]

    // And yet another
    class LeafNode[K,V] extends Node[K,V]

使用 -explaintypes -uniqid 并显式传递参数，我得到：

<console>:13: error: type mismatch;
 found   : Btree#31335.this.DefaultOrder#31343.type (with underlying type object Btree#31335.this.DefaultOrder#31344)
 required: Ordering#3222[K#31346]
               abstract class Node[K,V] extends TreeMap[K,V]()(DefaultOrder)
                                                               ^
Btree#31335.this.DefaultOrder#31343.type <: Ordering#3222[K#31346]?
  object Btree#31335.this.DefaultOrder#31344 <: scala.math.Ordering#11986[K#31346]?
    scala.math.Ordering#11986[K#31336] <: scala.math.Ordering#11986[K#31346]?
      K#31346 <: K#31336?

Answer 2

编译后，它呈现出两种变体，一种使用 Ordered 键 (K)，另一种使用键上的 Ordering：

package disttree {
    import scala.collection.immutable.TreeMap
    import scala.math.{Ordered, Ordering}

//  class Btree[K <% Ordered[K], V](fanout:Int) // Using Ordered
    class Btree[K : Ordering, V](fanout:Int)    // Using Ording
    {
    /* Using Ordered
        implicit object DefaultOrder extends Ordering[K] {
            def compare(k1: K, k2: K) = k1 compareTo k2
        }
    */

    /* Using Ordering */
        val keyOrdering = implicitly[Ordering[K]]

        implicit object DefaultOrder extends Ordering[K] {
            def compare(k1: K, k2: K) = keyOrdering.compare(k1, k2)
        }

        abstract class Node extends TreeMap[K,V]

        class InnerNode extends Node

        class LeafNode extends Node

        val root = new InnerNode()

        def search(n: Node, key: K): Option[(K,V)] = {
            return n.find(_ == key)
        }

        def insert(key: K, value: V) { }

        def delete(key: K) { }
    }
}

import disttree._;
object Tester {
    def main(args: List[String]) = {
        var t = new Btree[Int, Any](2)
        t.insert(1, "goodbye")
        Console.println(t)
    }
}