如何在Scala中按字典顺序对列表集合进行排序? [英] How do I sort a collection of Lists in lexicographic order in Scala?

问题描述

如果A具有Ordered[A]特质，我希望能够拥有像这样工作的代码

If A has the Ordered[A] trait, I'd like to be able to have code that works like this

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

，然后从列表中按字典顺序对列表进行排序.当然，仅仅因为A具有特征Ordered[A]并不意味着List[A]具有特征Ordered[List[A]].但是，大概可以做到这一点的标量方法"是使用隐式定义.

and get something where the lists have been sorted in lexicographic order. Of course, just because A has the trait Ordered[A] doesn't mean that List[A] has the trait Ordered[List[A]]. Presumably, however, the 'scala way' to do this is with an implicit def.

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

How do I implicitly convert a List[A] to a Ordered[List[A]], assuming A has the trait Ordered[A] (so that the code above just works)?

我已经考虑在List[A]对象上使用字典顺序，但是我希望代码可以适应其他顺序.

I have in mind using the lexicographic ordering on List[A] objects, but I'd like code that can be adapted to others orderings.

推荐答案

受本·林斯(Ben Lings)的回答启发，我编写了自己的sort版本:

Inspired by Ben Lings' answer, I wrote my own version of 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]].

Note that ordering is implicitly converted to 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:

It was asked how to supply your own comparison function (say, _ > _ instead of _ < _). It suffices to use 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实例的另一种类型.考虑到元组也是有序的，这对于案例类的字典比较是有用的.

Ordering.by allows you to map your value into another type for which there is already an Ordering instance. Given that also tuples are ordered, this can be useful for lexicographical comparison of case classes.

举个例子，让我们定义一个Int的包装，应用Ordering.by(_.v)，其中_.v提取基础值，并表明我们获得了相同的结果:

To make an example, let's define a wrapper of an Int, apply Ordering.by(_.v), where _.v extracts the underlying value, and show that we obtain the same result:

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)))

最后，让我们在具有更多成员的case类上做同样的事情，为Tuples重用比较器:

Finally, let's do the same thing on a case class with more members, reusing the comparators for Tuples:

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版中已弃用:

My definition of sort above is deprecated in 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
}

这篇关于如何在Scala中按字典顺序对列表集合进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！