10

OrderingScala的特征不是逆变的有什么原因吗？下面是一个鼓舞人心的例子。

假设我要执行有序插入。我可能有一个带有签名的功能

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

在这里，我有一个Ordering接受超类型的 type 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)
}

我希望我的 insert 函数可以与typesList[CodeTree]或. 但是，由于不是逆变的，我需要为每个.List[Leaf]List[Fork]OrderingOrderingscase

如果我定义

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

一切都按预期工作。

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

编辑：

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

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]实例定义一个隐式工厂函数。

4

2 回答 2

5

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

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

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

因此，如果可用，它将选择“最具体”的排序Ordering[Any]。

关于 scala 语言组上的逆变参数定义“特异性”的方式似乎正在进行一场大讨论。

于 2013-04-17T11:13:11.113 回答
3

在当前的 API 中，这些方法阻止了它的逆变：

  /** 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
于 2013-04-17T10:55:56.643 回答