Scala:订购方差 [英] Scala: Ordering contravariance

问题描述

Scala的 Ordering 特性不是协变的吗?一个激励人心的例子如下.

Is there any reason why Scala's Ordering trait is not contravariant? A motivating example follows.

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

Suppose I want to perform an ordered insert. I may have a function with the signature

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

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

Here, I have an Ordering which accepts super types of type A. I imagine this is useful when you're dealing with case classes. For example:

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 并非不变，因此我需要为每个 case 定义隐式的 Orderings .

I would want my insert function to work with types List[CodeTree], List[Leaf] or List[Fork]. However, as Ordering isn't contravariant, I need to define implicit Orderings for each case.

如果我定义

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

一切正常.

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

Is there any other way to achieve my goal?

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

My current solution is to define insert as

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

在处理 List [CodeTree] 时效果很好.我还定义了(受scalaz库启发):

which works fine when dealing with List[CodeTree]. I also define (inspired by the scalaz library):

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

I'm defining an implicit factory function for Ordering[A <: CodeTree] instances.

推荐答案

从上面注释中链接的"scala-language"线程中提取出更多详细答案.

A bit more of a detailed answer pulled out of the thread on 'scala-language' linked in the comment above.

Ordering 之所以不能互变的原因是，这与隐式解析中使用的特异性概念并不明智.隐式解析将尝试为参数选择最特定"的类型，如果它是其子类型，则认为一种类型比另一种类型更特定.这在协变情况下是有意义的:我宁愿对我的字符串列表有一个特定的隐式，而不是对任何旧列表都使用一个隐式的.但是，在相反情况下，它想要选择错误的东西:

The reason that Ordering is not contravariant is that this doesn't accord sensibly with the notion of specificity used in implicit resolution. Implicit resolution will try to pick the most 'specific' type for a parameter, and considers one type to be more specific than another if it's a subtype of it. This makes sense in covariant cases: I'd rather have an implicit specific to my list of strings than one for any old list. In contravariant cases, however, it wants to pick the wrong thing:

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

因此，它将选择最具体的"排序，如果可以的话，选择 Ordering [Any] .

And so it will pick the 'most specific' ordering as being, if available, Ordering[Any].

似乎有一个大讨论还在不断变化在scala语言组中针对反参数定义特异性"的方式.

There looks to be a big discussion going on changing the way 'specificity' is defined with regard to contravariant parameters on the scala-language group.

这篇关于Scala:订购方差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！