为什么 Scala 列表没有排序？

Question

Scala 中的列表没有隐式排序是否有原因？

val lists = List(List(2, 3, 1), List(2, 1, 3))
lists.sorted

error: could not find implicit value for parameter ord: Ordering[List[Int]]

编辑

是的，我的问题是为什么没有已经隐含在范围内的内置排序。对我来说，显然第二个列表应该“小于”第一个列表，因为 0 处的项目相等，而第二个列表的 1 处的项目较低。我想知道是否可能没有好的答案，当列表有两种不同的大小。

Answer 1

我认为这是一个疏忽。字典顺序对 Seq 确实有意义。我们应该将它添加到标准库中。

Answer 2

顺便说一句，即使在我修复此问题之前，您也可以通过其他方式执行此操作：

scala> List[Iterable[Int]](List(2, 3, 1), List(2, 1, 3)).sorted
res0: List[Iterable[Int]] = List(List(2, 1, 3), List(2, 3, 1))

scala> List(List(2, 3, 1), List(2, 1, 3)).sorted(Ordering[Iterable[Int]])
res1: List[List[Int]] = List(List(2, 1, 3), List(2, 3, 1))

但现在它的工作原理就像您希望的那样。

编辑：由于必要隐含的粗略分歧问题，我将其移出了默认范围。具有像这样跨越界限的隐式转换：

implicit def SeqDerived[CC[X] <: collection.Seq[X], T](implicit ord: Ordering[T]): Ordering[CC[T]]

...是潜在的问题根源。它将在 2.9 中可用，但您必须按如下方式导入它。

scala> val lists = List(List(2, 3, 1), List(2, 1, 3))
lists: List[List[Int]] = List(List(2, 3, 1), List(2, 1, 3))

scala> lists.sorted
<console>:9: error: could not find implicit value for parameter ord: Ordering[List[Int]]
       lists.sorted
             ^

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

scala> lists.sorted
res1: List[List[Int]] = List(List(2, 1, 3), List(2, 3, 1))

Answer 3

您拥有的是列表的列表，而不是整数的列表。您缺少的是确定列表是否<=另一个列表的标准。

这就是错误消息的内容：我找不到将列表与另一个列表进行比较的方法，您应该明确提供一个。

如果您的问题是“为什么列表没有与其他列表的内置比较方法”，那么，事情就是这样。

Answer 4

List[Int] 类上唯一真正合理的总顺序是字典顺序（即比较列表的第一个元素，如果它们相等则比较第二个元素，如果秒相等则比较第三个元素，等等）。标准库没有提供这一点，可能是因为实际需要它的情况并不多。创建从 List[X] 到 Ordering[List[X]] 的隐式转换来实现它是很容易的，然后您可以在需要的地方简单地导入该转换。

Answer 5

您可以使用 sortWith。这不会考虑不同大小的列表，因为 zip 会消除差异，但我认为它的作用类似于您所追求的：

lists.sortWith((a,b) => {
  a.zip(b).filterNot(x => x._1 == x._2) match {
    case Nil => true
    case t => t._1 < t._2
  }
})

Answer 6

Scala 2.13.3 - 调用 sorted 方法对我有用：

import scala.math.Ordering.Implicits.seqOrdering
val lists = List(List(2, 3, 1), List(2, 1, 3))
print(lists.sorted)   // prints List(List(2, 1, 3), List(2, 3, 1)) 

sorted 方法是 StrictOptimizedSeqOps 特征的成员，：

override def sorted[B >: A](implicit ord: Ordering[B]): C

Answer 7

在较新的 Scala 版本中（使用 2.12.5 进行测试）有一个 对 Iterable[A] 进行排序。只需将正确的类型赋予变量 lists：

scala> val lists = List(List(2, 3, 1), List(2, 1, 3))
lists: List[List[Int]] = List(List(2, 3, 1), List(2, 1, 3))

scala> (lists: List[Iterable[Int]]).sorted
res0: List[Iterable[Int]] = List(List(2, 1, 3), List(2, 3, 1))

或者将元素转换为 Iterable[] 的实例（这对于 List[] 实例来说是无操作的） ）：

scala> lists.map(_.toIterable).sorted
res1: List[Iterable[Int]] = List(List(2, 1, 3), List(2, 3, 1))