11

我一直在阅读 Scala 中的类型类，并认为自己掌握得很好，直到我想起了 Java 的java.util.Comparator.

如果我理解正确，Ordering是类型类的原型示例。Comparator我能想到的 a和 an instance之间的唯一区别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);
}
4

3 回答 3

10

我不想专门谈论类型类，而是谈论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为您可能喜欢的类提供 s，但您可以定义自己的：

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，它与任何东西一样都是类型类。

于 2013-10-21T21:43:54.780 回答
5

术语类型类来自 Haskell，它们是语言的一部分。在 scala 中，它不是，它更像是一种模式，恰好在 scala 中有很多语言支持（主要是隐式）。即使没有这种语法支持，该模式也有意义，例如在 java 中，我想说这Comparator是该模式的典型示例（尽管 java 中不使用术语类型类）。

从面向对象的角度来看，该模式在于拥有Comparator而不是Comparable. 最基本的对象思维会在对象中有比较服务，比如说class String implements Comparable<String>。但是，提取它有许多优点：

  • 您可以为无法更改其代码的类提供服务（例如，数组）
  • 您可以提供不同的服务实现（有无数种比较字符串的方法（不区分大小写，并且依赖于许多语言）。人们可能会按姓名、年龄等进行排序。而且，您可能只需要排序逆转。

这两个原因在java中已经足够了Comparable，并且在排序集合（例如TreeSet）中使用它们Comparable被保留，因为它提供了一个方便的默认值（当你想要“默认”比较时不需要传递一个比较器，它更容易调用（x.compareTo（y）而不是comparator.compare（x，y））。在scala中，使用隐式，这些原因都不是令人信服的（与java的互操作性仍然是在scala中实现Ordered/Comparable的原因） .

类型类还有其他不太明显的优势。其中 ：

  • 类型类实现是可用的，即使您没有它所操作的类型的实例，它也可能很有用。考虑操作sum(list)。它要求列表的元素上有某种可用的添加。这可能在元素本身中可用。说他们可能是Addable[T]一些def add(other: T): T。但是，如果将空列表传递给 sum，它应该返回列表类型的“零”（0 表示整数，空字符串表示字符串......）。有一个def zero: TinAddable[T]是没有用的，因为在那一刻，你没有Addable周围。但这适用于诸如Numericor之类的类型类Monoid。
  • 由于类型类被具体化（它们是对象而不是方法），它们是第一类，您可以组合它们，转换它们。一个非常简单的示例是反转排序（您也可以在 Comparable 上实现它，在 java 中可能在静态方法中）。您可以将Int和的排序结合起来，String在该对上定义一个排序(Int, String)，或者给定一个Orderingon T，建立一个排序 on List[T]。Scala 使用隐式来做到这一点，但它在 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 中更是如此，但仍然如此）

  • 您必须在方法之间传递类型类实例。在 scala 中使用隐式参数或 [T : Comparable] 约束要容易得多，但是如果不在调用站点，则必须在方法定义中写入一些内容，并且在运行时，必须传递参数。
  • 一切都必须在编译时设置（即使是在隐式设置的 scala 中，所以虽然你可以尝试if(x is Comparable<?>) {do some sorting}，但使用 Comparator 是不可能的。
于 2013-10-21T22:00:27.840 回答
0

没有 java.util.Comparator 是一个接口

public interface Comparator<T>

一个比较函数，它对某些对象集合进行总排序。比较器可以传递给排序方法（例如 Collections.sort 或 Arrays.sort），以允许精确控制排序顺序。比较器还可用于控制某些数据结构（例如排序集或排序图）的顺序，或为不具有自然排序的对象集合提供排序。

于 2013-10-21T16:44:17.157 回答