Scala: Order controvarianze

Question

C'è qualche ragione per cui il tratto di Scala Ordering non è controverso? Segue un esempio motivante.

Supponiamo di voler eseguire un inserto ordinato. Io possa avere una funzione con la firma

def insert[A, B >: A](list: List[A], item: A)(implicit ord: Ordering[B]): List[A] 

Qui, ho un Ordering che accetta di super tipi di tipo A. Immagino sia utile quando hai a che fare con case classes. Per esempio:

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

vorrei la mia funzione di inserimento al lavoro con i tipi List[CodeTree], List[Leaf] o List[Fork]. Tuttavia, poiché Ordering non è controverso, è necessario definire implicito Orderings per ogni case.

Se io definisco

trait MyOrdering[-A] { 
    def compare(a: A, b: A): Int 
} 

tutto funziona come previsto.

C'è qualche altro modo per raggiungere il mio obiettivo?

EDIT:

mia soluzione attuale è quello di definire inserto come

def insert[A](list: List[A], item: A)(implicit ord: Ordering[A]): List[A] 

che funziona bene quando si tratta di List[CodeTree]. Ho anche definisco (ispirato dalla libreria scalaz):

trait Contravariant[F[_]] { 
    def contramap[A, B](r: F[A], f: B => A): F[B] 
} 

implicit object OrderingContravariant extends Contravariant[Ordering] { 
    def contramap[A, B](r: Ordering[A], f: B => A) = r.on(f) 
} 

implicit def orderingCodeTree[A <: CodeTree]: Ordering[A] = 
    implicitly[Contravariant[Ordering]].contramap(CodeTreeOrdering, identity) 

Sto definendo una funzione di fabbrica implicito per Ordering[A <: CodeTree] istanze.

Answer 1

Un po 'più di una risposta dettagliata estratta dal filo su 'scala-linguaggio' collegato nel commento sopra.

La ragione per cui Ordering non è controvariante è che ciò non concorda in modo ragionevole con la nozione di specificità utilizzata nella risoluzione implicita. La risoluzione implicita proverà a scegliere il tipo più "specifico" per un parametro e considera un tipo più specifico di un altro se si tratta di un sottotipo. Questo ha senso nei casi covarianti: preferirei avere un implicito specifico per la mia lista di stringhe piuttosto che uno per una vecchia lista. In casi controvarianti, tuttavia, si vuole raccogliere la cosa sbagliata:

trait Ord[-A] 
A <: B 
Ord[B] <: Ord[A] 

E così si riprenderà l'ordinamento 'più specifica' come, se disponibile, Ordering[Any].

Sembra esserci un big discussion che cambia il modo in cui viene definita la "specificità" per quanto riguarda i parametri controvarianti nel gruppo scala-language.

Answer 2

Nel API corrente, questi metodi impedire essere contravariant:

/** Return `x` if `x` >= `y`, otherwise `y`. */ 
    def max(x: T, y: T): T = if (gteq(x, y)) x else y 

    /** Return `x` if `x` <= `y`, otherwise `y`. */ 
    def min(x: T, y: T): T = if (lteq(x, y)) x else y