如何在Scala中按字典顺序对列表集合进行排序？

Question

如果A有Ordered[A]特征,我希望能够拥有像这样的代码

val collection: List[List[A]] = ... // construct a list of lists of As
val sorted = collection sort { _ < _ }

并获得列表按字典顺序排序的内容.当然,仅仅因为A具有特征Ordered[A]并不意味着List[A]具有特征Ordered[List[A]].然而,据推测,执行此操作的"scala方式"是隐式def.

我如何隐式地将a转换List[A]为a Ordered[List[A]],假设A具有特征Ordered[A](以便上面的代码可以正常工作)？

我记得在List[A]对象上使用词典排序,但我想要的代码可以适应其他顺序.

Answer 1

灵感来自Ben Lings的回答,我设法找出了一种似乎最简单的按字典顺序对列表进行排序的方法:添加行

import scala.math.Ordering.Implicits._

在进行List [Int]比较之前,确保隐式函数infixOrderingOps在范围内.

Answer 2

(11分钟前我实际上不知道该怎么做,我希望能回答我自己的问题.)

implicit def List2OrderedList[A <% Ordered[A]](list1: List[A]): Ordered[List[A]] = { 
    new Ordered[List[A]] {
        def compare(list2: List[A]): Int = {
            for((x,y) <- list1 zip list2) {
                val c = x compare y
                if(c != 0) return c
            }
            return list1.size - list2.size
        }
    }
}

这里需要注意的一个重要事项是" 视图绑定 " A <% Ordered[A],它确保A不需要它本身Ordered[A],只是有一种方法可以进行这种转换.令人高兴的是,Scala库的对象Predef具有从Ints到RichInts 的隐式转换,特别是Ordered[Int]s.

其余的代码只是实现了词典排序.

Answer 3

受到 Ben Lings 回答的启发，我写了自己的版本sort：

def sort[A : Ordering](coll: Seq[Iterable[A]]) = coll.sorted

这相当于：

def sort[A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A]) = coll.sorted

请注意，ordering被隐式转换为Ordering[Iterable[A]].

例子：

scala> def sort[A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A]) = coll.sorted
sort: [A](coll: Seq[Iterable[A]])(implicit ordering: Ordering[A])Seq[Iterable[A]]

scala> val coll = List(List(1, 3), List(1, 2), List(0), Nil, List(2))
coll: List[List[Int]] = List(List(1, 3), List(1, 2), List(0), List(), List(2))

scala> sort(coll)
res1: Seq[Iterable[Int]] = List(List(), List(0), List(1, 2), List(1, 3), List(2))

有人询问如何提供自己的比较函数（例如，_ > _而不是_ < _）。使用就足够了Ordering.fromLessThan：

scala> sort(coll)(Ordering.fromLessThan(_ > _))
res4: Seq[Iterable[Int]] = List(List(), List(2), List(1, 3), List(1, 2), List(0))

Ordering.by允许您将值映射到已有 Ordering 实例的另一种类型。鉴于元组也是有序的，这对于案例类的词典比较很有用。

举个例子，让我们定义一个 Int 的包装器 apply Ordering.by(_.v)，在其中_.v提取底层值，并表明我们获得了相同的结果：

scala> case class Wrap(v: Int)
defined class Wrap

scala> val coll2 = coll.map(_.map(Wrap(_)))
coll2: List[List[Wrap]] = List(List(Wrap(1), Wrap(3)), List(Wrap(1), Wrap(2)), List(Wrap(0)), List(), List(Wrap(2)))

scala> sort(coll2)(Ordering.by(_.v))
res6: Seq[Iterable[Wrap]] = List(List(), List(Wrap(0)), List(Wrap(1), Wrap(2)), List(Wrap(1), Wrap(3)), List(Wrap(2)))

最后，让我们对具有更多成员的案例类执行相同的操作，重用元组的比较器：

scala> case class MyPair(a: Int, b: Int)
defined class MyPair

scala> val coll3 = coll.map(_.map(MyPair(_, 0)))
coll3: List[List[MyPair]] = List(List(MyPair(1,0), MyPair(3,0)), List(MyPair(1,0), MyPair(2,0)), List(MyPair(0,0)), List(), List(MyPair(2,0)))

scala> sort(coll3)(Ordering.by(x => (x.a, x.b)))
res7: Seq[Iterable[MyPair]] = List(List(), List(MyPair(0,0)), List(MyPair(1,0), MyPair(2,0)), List(MyPair(1,0), MyPair(3,0)), List(MyPair(2,0)))

编辑：

我对sort上面的定义在 2.13 中已被弃用：

warning: method Iterable in object Ordering is deprecated (since 2.13.0):
Iterables are not guaranteed to have a consistent order; if using a type
with a consistent order (e.g. Seq), use its Ordering (found in the
Ordering.Implicits object)

改用：

def sort[A](coll: Seq[Seq[A]])(implicit ordering: Ordering[A]) = {
  import Ordering.Implicits._
  coll.sorted
}