Orderings和TreeMap

Question

我正在构建一个MultiSet[A]，并使用一个TreeMap[A, Int]来跟踪元素。

class MultiSet[A <: Ordered[A] ](val tm: TreeMap[A, Int]) { ... }

现在，我想使用这个框架创建一个MultiSet[Int]。特别是，我想要一个方法，它将使用一个Vector[Int]并生成一个TreeMap[Int, Int]，我可以使用它来生成一个MultiSet[Int]。

我编写了以下vectorToTreeMap，它不带怨言地编译。

def vectorToTreeMap[A <: Ordered[A]](elements: Vector[A]): TreeMap[A, Int] =
  elements.foldLeft(new TreeMap[A, Int]())((tm, e) => tm.updated(e, tm.getOrElse(e, 0) + 1))

但当我尝试

val tm: TreeMap[Int, Int] = vectorToTreeMap(Vector(1, 2, 3))

我收到编译器抱怨说Int不符合A <: Ordered[A]。在这个上下文中创建TreeMap[Int, Int]需要做些什么？(我想要更一般的情况，因为MultiSet[A]并不总是MultiSet[Int]。)

我也尝试了A <: scala.math.Ordered[A]和A <: Ordering[A]，但是没有更好的结果。(我承认，我不明白这三种可能性之间的区别，以及在这种情况下是否重要。)

谢谢你的帮助。

Answer 1

问题是int是java的别名，它不实现OrderedInt。它怎么可能，因为java甚至不知道OrderedT特性的存在。

解决问题的方法有两种：

视图界

第一种方法是将约束<：更改为视图绑定<%。

def vectorToTreeMap[A <% Ordered[A]](elements: Vector[A]): TreeMap[A, Int] =
  elements.foldLeft(new TreeMap[A, Int]())((tm, e) => tm.updated(e, tm.getOrElse(e, 0) + 1))

<：OrderedA意味着方法vectorToTreeMap仅为直接实现OrderedA的类型定义，后者不包括Int。

<% OrderedA意味着为“可以视为”实现OrderedA的所有类型定义方法vectorToTreeMap，这包括Int，因为有从Int到OrderedInt的隐式转换

scala> implicitly[Int => Ordered[Int]]
res7: Int => Ordered[Int] = <function1>

类型类

第二种方法是不需要A类型的任何(直接或间接)继承关系，而只是要求有一种方法来排序类型A的实例。

基本上，您总是需要排序才能从向量创建一个TreeMap，但是为了避免每次调用方法时都传递它，您可以将排序作为一个隐式参数。

def vectorToTreeMap[A](elements: Vector[A])(implicit ordering:Ordering[A]): TreeMap[A, Int] =
  elements.foldLeft(new TreeMap[A, Int]())((tm, e) => tm.updated(e, tm.getOrElse(e, 0) + 1))

事实证明，对于所有java原语类型以及字符串，都有OrderingA实例，正如在scala中隐式方法中可以看到的那样：

scala> implicitly[Ordering[Int]]
res8: Ordering[Int] = scala.math.Ordering$Int$@5b748182

Scala甚至能够导出组合类型的顺序。例如，如果在每个元素类型都有排序的情况下有一个元组，scala也会自动为元组类型提供排序：

scala> implicitly[Ordering[(Int, Int)]]
res9: Ordering[(Int, Int)] = scala.math.Ordering$$anon$11@66d51003

使用所谓类型类的第二种方法要灵活得多。例如，如果您想要一棵普通的旧int树，但是使用反向顺序，您所要做的就是直接或作为隐式val提供一个反向int排序。

这种方法在惯用scala中也很常见。因此，它甚至有特殊的语法：

def vectorToTreeMap[A : Ordering](elements: Vector[A]): TreeMap[A, Int] = ???

等于

def vectorToTreeMap[A](elements: Vector[A])(implicit ordering:Ordering[A]): TreeMap[A, Int] = ???

这基本上意味着您希望只为存在排序的类型定义方法vectorToTreeMap，但您不关心为排序指定名称。即使使用简短的语法，也可以将vectorToTreeMap与隐式解析的OrderingA一起使用，也可以显式传递OrderingA。

第二种方法有两大优点：

• 它允许您为您不“拥有”的类型定义功能。
• 它允许您将某些方面的行为解耦，例如从类型本身排序，而通过继承方法将行为耦合到类型。例如，您可以对Sting进行正常排序和caseInsensitiveOrdering。但是，如果允许字符串从有序扩展，则必须决定一种排序行为。

这就是为什么scala集合本身使用第二种方法来为TreeMap提供排序。

编辑:下面是一个为没有排序的类型提供排序的示例：

scala> case class Person(name:String, surname:String)
defined class Person

scala> implicitly[Ordering[Person]]
<console>:10: error: No implicit Ordering defined for Person.
              implicitly[Ordering[Person]]
                        ^

Case类没有自动定义的顺序。但我们可以很容易地定义一个：

scala> :paste
// Entering paste mode (ctrl-D to finish)

case class Person(name:String, surname:String)

object Person {

  // just convert to a tuple, which is ordered by the individual elements
  val nameSurnameOrdering : Ordering[Person] = Ordering.by(p => (p.name, p.surname))

  // make the nameSurnameOrdering the default that is in scope unless something else is specified
  implicit def defaultOrdering = nameSurnameOrdering
}

// Exiting paste mode, now interpreting.

defined class Person
defined module Person

scala> implicitly[Ordering[Person]]
res1: Ordering[Person] = scala.math.Ordering$$anon$9@50148190