斯卡拉:订购逆转

Question

有什么理由说Scala的Ordering特性不是逆变的吗？一个激励性的例子如下.

假设我想执行有序插入.我可能有签名功能

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

在这里,我有一个Ordering接受超类型的A.我想这在你处理时很有用case classes.例如:

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

我希望我的插入函数可以使用类型List[CodeTree],List[Leaf]或者List[Fork].但是,由于Ordering不是逆变,我需要Orderings为每个定义隐式case.

如果我定义

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

一切都按预期工作.

有没有其他方法可以实现我的目标？

编辑:

我目前的解决方案是将insert定义为

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

在处理时工作正常List[CodeTree].我也定义了(灵感来自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)

我正在为Ordering[A <: CodeTree]实例定义隐式工厂函数.

Answer 1

从上面评论中链接的“scala-language”线程中提取了更多详细答案。

Ordering不是逆变的原因是这与隐式解析中使用的特异性概念不合情理。隐式解析将尝试为参数选择最“特定”的类型，并认为一种类型比另一种类型更具体（如果它是它的子类型）。这在协变情况下是有意义的：我宁愿有一个特定于我的字符串列表的隐式，而不是任何旧列表的一个。然而，在逆变的情况下，它想要选择错误的东西：

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

因此它会选择“最具体”的顺序，如果有的话，Ordering[Any].

似乎有一个很大的讨论正在改变关于 scala 语言组的逆变参数的“特异性”的定义方式。