Could not find implicit value for parameter ordering

Question

Hi,

I get the following error when trying to compile this:

Btree.scala:9: error: could not find implicit value for parameter ordering: Ordering[K] abstract class Node[K,V] extends TreeMap[K,V]

TreeMap is supposed to accept an implicit Ordering[A] val which I provide. Perhaps the implicit parameter needs to be in object Tester where the Btree(TreeMap) is instantiated? I would prefer to keep the implicit declaration inside of the Btree class because I would like Ordering to have a type K that implements Comparable[K]. Make sense?

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

This compiles and it exhibits two variants, one using Ordered keys (K) and the other using an Ordering on the keys:

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)
    }
}

Answer 2

Common mistake. These are two different K's:

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]

Using -explaintypes -uniqid and passing the parameter explicitly, I get this:

<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 3

Randall,

Thank you for the great answer. I have never seen this sort of 'bounded?' type declaration before:

[K : Ordering,V]

And I have not been able to find any documentation on it. Would I be correct in saying that this forces type K to be a supertype of type Ordering[K]?