如何对 List[Int] 对象进行排序？

Question

我希望你能够帮我在Scala中对List对象进行排序，而不是对列表中的元素进行排序。例如，如果我有两个Int类型的列表：

val l1 = List(1, 2, 3, 7)
val l2 = List(1, 2, 3, 4, 10)

我希望能按照 l1 > l2 的顺序排列它们。

我创建了一个 case class，它能够满足我的需求，但问题是当我使用它时，我的其他方法都不起作用。我需要在类中实现所有其他方法吗，比如 flatten、sortWith 等等？

我的类代码看起来像这样:

class ItemSet(itemSet: List[Int]) extends Ordered[ItemSet] {

  val iSet: List[Int] = itemSet

  def compare(that: ItemSet) = {

    val thisSize = this.iSet.size
    val thatSize = that.iSet.size
    val hint = List(thisSize, thatSize).min
    var result = 0
    var loop = 0

    val ths = this.iSet.toArray
    val tht = that.iSet.toArray

    while (loop < hint && result == 0) {
      result = ths(loop).compare(tht(loop))
      loop += 1
    }
    if (loop == hint && result == 0 && thisSize != thatSize) {
      thisSize.compare(thatSize)
    } else
      result
  }

}

现在，如果我创建一个ItemSets的数组，我可以对它进行排序：

val is1 = new ItemSet(List(1, 2, 5, 8))
val is2 = new ItemSet(List(1, 2, 5, 6))
val is3 = new ItemSet(List(1, 2, 3, 7, 10))

Array(is1, is2, is3).sorted.foreach(i => println(i.iSet))

scala> List(1, 2, 3, 7, 10)
List(1, 2, 5, 6)
List(1, 2, 5, 8)

我遇到问题的两种方法是：

def itemFrequencies(transDB: Array[ItemSet]): Map[Int, Int] = transDB.flatten.groupBy(x => x).mapValues(_.size)

我收到的错误信息是：

类型为 Map[Nothing, Int] 的表达式与预期类型 Map[Int, Int] 不符

这个错误信息的意思是，你的代码中使用了类型为 Map[Nothing, Int] 的表达式，但实际上需要的是类型为 Map[Int, Int] 的表达式。

def sortListAscFreq(transDB: Array[ItemSet], itemFreq: Map[Int, Int]): Array[List[Int]] = {
  for (l <- transDB) yield
    l.sortWith(itemFreq(_) < itemFreq(_))
}

我得到的是：

无法解决符号sortWith。

有没有一种方法可以扩展List[Int]，以便我可以对列表集合进行排序，而不会失去其他方法的功能？

- Mike Lavender

Answer 1

标准库为有序集合提供了一种词典排序的方式。只需将其引入作用域即可。 （链接）

scala> import scala.math.Ordering.Implicits._
import scala.math.Ordering.Implicits._

scala> val is1 = List(1, 2, 5, 8)
is1: List[Int] = List(1, 2, 5, 8)

scala> val is2 = List(1, 2, 5, 6)
is2: List[Int] = List(1, 2, 5, 6)

scala> val is3 = List(1, 2, 3, 7, 10)
is3: List[Int] = List(1, 2, 3, 7, 10)

scala> Array(is1, is2, is3).sorted foreach println
List(1, 2, 3, 7, 10)
List(1, 2, 5, 6)
List(1, 2, 5, 8)

Ordering 类型类在 Scala 中比 Ordered 更方便使用——它允许你指定某个已有类型的排序方式，而无需更改其代码或创建扩展 Ordered[Whatever] 的代理类，正如你所见，这可能会很快变得混乱。

- Travis Brown

---

非常感谢！我简直不敢相信我竟花了两天时间来尝试让所有东西都正常工作。 - Mike Lavender

@Val，我猜那是讽刺，但你有点错过了重点——在调用.sorted之前，列表的数组_没有_排序，然后它被排序了。此外，我只是使用OP的示例，这通常是一个好主意。 - Travis Brown