Comparator是一个类型类吗？

Question

我一直在阅读Scala中的类型类,并认为我对它有很好的把握,直到我记得Java java.util.Comparator.

如果我理解正确,Ordering是类型类的原型示例.我可以在a Comparator和实例之间想到的唯一区别Ordering是比较器必然是显式的,而排序可以是,而且往往是隐含的.

是Comparator一个类型？我得到(错误的？)印象,Java实际上没有类型类.这是否意味着类型类需要能够隐式？我认为类型类的隐式转换主要是语法糖 - 实际上很棒,它"简单地"给编译器足够的提示 - 我错过了什么？

---

下面的代码示例显示了如何Comparator将排序操作添加到没有它的类型,而无需修改所述类型.

// Comparator used to retroactively fit the MyExample class with an ordering operation.
public static class MyExampleComparator implements Comparator<MyExample> {
    public static final Comparator<MyExample> SINGLETON = new MyExampleComparator();

    private MyExampleComparator() {}

    public int compare(MyExample a, MyExample b) {
        return a.value - b.value;
    }
}

// Custom type, its only purpose is to show that Comparator can add an ordering operation to it when it doesn't
// have one to begin with.
public static class MyExample {
    private final int value;

    public MyExample(int v) {
        value = v;
    }

    public String toString() {
        return Integer.toString(value);
    }
}

public static void main(String... args) {
    List<MyExample> list = new ArrayList<MyExample>();

    for(int i = 0; i < 10; i++)
        list.add(new MyExample(-i));

    // Sorts the list without having had to modify MyExample to implement an interface.
    Collections.sort(list, MyExampleComparator.SINGLETON);

    // Prints the expected [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0]
    System.out.println(list);
}

Answer 1

我不想特别谈论类型类,而是谈论Scala中的类型类模式 ; 原因是当你开始询问"什么是类型类"时,你最终得出的结论是它只是一个以特定方式使用的接口.

(在Haskell中,将特定构造称为类型类更有意义.)

类型类模式由三个基本部分组成(但为方便起见,通常还有一些部分).第一种是由单一类型参数化的接口,它在参数化类型上抽象出某种能力. java.util.Comparator是一个很好的例子:它提供了一个比较界面.我们就这样用吧.

您需要的第二件事是使用该参数化的方法,您可以在Scala中使用简写符号指定:

// Short signature
//             v------------------- "We must be able to find a Comparator for A"
def ordered[A: java.util.Comparator](a0: A, a1: A, a2: A) = {
  val cmp = implicitly[java.util.Comparator[A]]   // This is the Comparator
  cmp.compare(a0, a1) <= 0 && cmp.compare(a1, a2) <= 0
}

// Long signature version
def ordered[A](a0: A, a1: A, a2: A)(implicit cmp: java.util.Comparator[A]) = {
  cmp.compare(a0, a1) <= 0 && cmp.compare(a1, a2) <= 0
}

好的,但你从哪里得到那个比较器？这是第三个必要的部分.默认情况下,Scala不会为您Comparator提供您可能喜欢的类,但您可以定义自己的类:

implicit object IntComp extends java.util.Comparator[Int] {
  def compare(a: Int, b: Int) = a.compareTo(b)
}

scala> ordered(1,2,3)
res5: Boolean = true

scala> ordered(1,3,2)
res6: Boolean = false

现在您已经Int(隐式)提供了功能,编译器将填充隐式参数ordered以使其工作.如果您尚未提供该功能,则会出错:

scala> ordered("fish","wish","dish")
<console>:12: error: could not find implicit value
for parameter cmp: java.util.Comparator[String]
          ordered("fish","wish","dish")

直到你提供该功能:

implicit object StringComp extends java.util.Comparator[String] {
  def compare(a: String, b: String) = a.compareTo(b)
}

scala> ordered("fish","wish","dish")
res11: Boolean = false

那么,我们称之为java.util.Comparator类型类吗？它当然与处理类型类模式的等效部分的Scala特征一样起作用.因此,即使类型类模式在Java中不能正常工作(因为您必须显式指定要使用的实例而不是隐式查找它),从Scala的角度来看java.util.Comparator,它与任何类型都是类型类.

Answer 2

术语类型类来自Haskell,因为它们是语言的一部分.在scala中,它不是,它更像是一种模式,恰好在scala中有很多语言支持(主要是隐含).即使没有这种语法支持,该模式也是有意义的,例如在java中,我会说那Comparator是那种模式的典型例子(尽管在java中没有使用术语类型类).

从面向对象的角度来看,模式包括Comparator而不是Comparable.比如说,最基本的对象思想就是在对象中使用比较服务class String implements Comparable<String>.但是,提取它有很多优点:

• 您可以为无法更改其代码的类提供服务(例如,数组)
• 您可以提供不同的服务实现(有很多方法可以比较字符串(不区分大小写和许多依赖于语言的方法).人们可能会根据他们的姓名,年龄等等进行排序.而且,您可能只想要一个订购逆转.

这两个原因足以Comparable在java中使用,并且在排序集合(例如TreeSet)中使用它们Comparable,因为它提供了一个方便的默认值(当你想要"默认"比较时不需要传递Comparator,并且它更容易调用(x.compareTo(y)而不是comparator.compare(x,y)).在scala中,带有implicits,这一点都没有引人注目(与java的互操作性仍然是在scala中实现Ordered/Comparable的原因) .

键入类还有其他不太明显的优点.其中 :

• 类型类实现可用,即使您没有操作类型的实例,它也可能很有用.考虑操作sum(list).它要求在列表的元素上有某种可用的附加内容.这可能在元素本身中可用.说他们可能是一些Addable[T]有def add(other: T): T.但是如果你将空列表传递给sum,它应该返回列表类型类型的"零"(0表示整数,空字符串表示字符串......).有一个def zero: Tin Addable[T]会没用,就像那一刻,你没有Addable.但这适用于类型类,如Numeric或Monoid.
• 由于类型类是被赋予的(它们是对象而不是方法)它们是第一类,你可以组合它们,转换它们.一个非常简单的例子是反转Ordering(你也可以在Comparable上实现它,在java中可能是静态方法).您可以组合的排序Int,并String有对对定义的顺序(Int, String),或给予Ordering上T,建立一个有序的List[T].Scala用implicits做到了这一点,但它在java中仍然有意义.

一个更复杂的例子:

// Comparison  by the first comparator which finds the two elements different. 
public static Comparator<T> lexicographic<T>(final Comparator<T>... comparators) {
   return new Comparator<T>() {
      public int compare(T t1, T t2) {
         for(comparator : comparators) {
            int result = comparator.compare(t1, t2);
            if (result != 0) return result;
         }
         return 0;
      }
   }
}

(在scala中可能更简单,但同样,这在java中很有用)

还有一些小的缺点(在Java中比在scala中更多,但仍然存在)

• 您必须将类型类实例从方法传递给方法.使用隐式参数或[T:Comparable]约束在scala中更容易,但是,如果不在调用站点,则必须在方法定义中编写某些内容,并且在运行时,必须传递参数.
• 一切都必须在编译时设置(即使在scala中隐式设置它)所以当你可以尝试时if(x is Comparable<?>) {do some sorting},这对于比较器来说是不可能的.