title: Scala: Ordering contravariance
body: <p>Is there any reason why Scala's <code>Ordering</code> trait is not contravariant? A motivating example follows.</p>
  
  <p>Suppose I want to perform an ordered insert. I may have a function with the signature</p>
  
  <pre><code>def insert[A, B &gt;: A](list: List[A], item: A)(implicit ord: Ordering[B]): List[A]
  </code></pre>
  
  <p>Here, I have an <code>Ordering</code> which accepts super types of type <code>A</code>. I imagine this is useful when you're dealing with <code>case classes</code>. For example:</p>
  
  <pre><code>abstract class CodeTree
  case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree
  case class Leaf(char: Char, weight: Int) extends CodeTree
  
  def weight(tree: CodeTree): Int 
  def chars(tree: CodeTree): List[Char] 
  
  implicit object CodeTreeOrdering extends Ordering[CodeTree] {
    def compare(a: CodeTree, b: CodeTree): Int = weight(a) compare weight(b)
  }
  </code></pre>
  
  <p>I would want my insert function to work with types <code>List[CodeTree]</code>, <code>List[Leaf]</code> or <code>List[Fork]</code>. However, as <code>Ordering</code> isn't contravariant, I need to define implicit <code>Orderings</code> for each <code>case</code>.</p>
  
  <p>If I define</p>
  
  <pre><code>trait MyOrdering[-A] {
    def compare(a: A, b: A): Int
  }
  </code></pre>
  
  <p>everything works as expected.</p>
  
  <p>Is there any other way to achieve my goal?</p>
  
  <p>EDIT:</p>
  
  <p>My current solution is to define insert as </p>
  
  <pre><code>def insert[A](list: List[A], item: A)(implicit ord: Ordering[A]): List[A]
  </code></pre>
  
  <p>which works fine when dealing with <code>List[CodeTree]</code>. I also define (inspired by the scalaz library):</p>
  
  <pre><code>trait Contravariant[F[_]] {
    def contramap[A, B](r: F[A], f: B =&gt; A): F[B]
  }
  
  implicit object OrderingContravariant extends Contravariant[Ordering] {
    def contramap[A, B](r: Ordering[A], f: B =&gt; A) = r.on(f)
  }
  
  implicit def orderingCodeTree[A &lt;: CodeTree]: Ordering[A] =
    implicitly[Contravariant[Ordering]].contramap(CodeTreeOrdering, identity)
  </code></pre>
  
  <p>I'm defining an implicit factory function for <code>Ordering[A &lt;: CodeTree]</code> instances.</p>