Implicit resolution, Ordered and Ordering

Thanks to my new four day work week setup (a mixed blessing, but
rather nice) I finally have time to give the collections API the kick
around I've been promising. :-)

I've been investigating some of the Ordering stuff to start with (I'm
updating TreeSet to use Ordering, thus keeping it in line with TreeMap
and giving it shiny new bonus performance goodness). I ran into some
problems.

Some of them are just cases where a conversion has been passed
explicitly. Those are fortunately the work of moments to fix and can
safely be ignored.

The more problematic case is things where an existing class has
explicitly extended Ordered[MyClass]. These don't automatically get an
Ordering, which is a bit of a pain.

Ok, I thought this would be simple to solve by just adding the
following implicit to Ordering:

implicit def OrderedOrdering[A <: Ordered[A]] : Ordering[A] = new Ordering[A]{
def compare(x : A, y : A) = x.compare(y);
}

But unfortunately this introduces an implicit ambiguity:

scala> Ordering[Int]
:5: error: ambiguous implicit values:
both value Int in object Ordering of type => Ordering[Int]
and method OrderedOrdering in object Ordering of type [A <:
Ordered[A]]Ordering[A]
match expected type Ordering[Int]
Ordering[Int]
^

This is particularly perplexing because Int is not <: Ordered[Int]! It
only has an implicit conversion to it. But even without that, I had
been under the impression that something like this should work. Simple
examples like the following certainly work fine without any ambiguity:

trait Foo[T];
class Bar extends Foo[Bar];

class Kitten[T]{
override def toString = "meow"
}
object Kitten{
def apply[T](implicit kitten : Kitten[T]) = kitten;

implicit def KittensForFoo[T <: Foo[T]] : Kitten[T] = new Kitten[T];
implicit val KittenForBar : Kitten[Bar] = new Kitten[Bar];
}

object Test{
def main(args : Array[String]){
val kitten = Kitten[Bar];
println(kitten);
}
}

So I'm not quite sure what's going on here!

I can work around this issue for now, but this seems like something
that needs to be resolved (I'd try to do it myself, but I'm
sufficiently fuzzy on the details of the implicit resolution
implementation that I don't want to get bogged down in this given
limited time to play with the collections implementation).