如何按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。

我如何隐式转换 List[A] 到 Ordered[List[A]], ，假设A具有特征 Ordered[A] （因此上面的代码只是有效的）吗？

我牢记使用词典订购 List[A] 对象，但我希望可以适应其他订单的代码。

Answer 1

受本·林斯（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))

被问到如何提供自己的比较功能；使用订购就足够了。

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

Ordering.by 允许您将您的值映射到已经存在订购实例的另一种类型中。鉴于该元素也被排序，这对于案例类的词典比较可能很有用。

举一个例子，让我们定义一个int的包装器，应用 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)))

Answer 2

受本·林斯（Ben Lings）的回答的启发，我设法弄清楚了在词典上排序列表的最简单方法：添加行

import scala.math.Ordering.Implicits._

在进行列表[int]比较之前，以确保隐式函数 infixOrderingOps 处于范围。

Answer 3

（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 4

在2.8中，您应该只能做 collection.sorted. sorted 采用隐式 Ordering 范围。任何实施的类型 Ordered 有一个相应的 Ordering （感谢隐性转换 Ordering.ordered）。也有隐式 Ordering.Iterable 这使得 Iterable[T] 有一个 Ordering 如果 T 有一个 Ordering.

但是，如果您尝试使用它，则无效：

scala> def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted

<console>:5: error: could not find implicit value for parameter ord: Ordering[List[A]]
       def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted
                                                             ^

您需要明确指定您想要的 Ordering[Iterable[A]]:

def sort[A <: Ordered[A]](coll: List[List[A]]) = coll.sorted[Iterable[A]]

我不确定为什么编译器找不到 Ordering[Iterable[A]] 如果该集合的元素类型是 List[A].

Answer 5

受丹尼尔评论的启发，这是一个递归版本：

implicit def toOrdered[A <% Ordered[A]](list1: List[A]): Ordered[List[A]] = { 
  @scala.annotation.tailrec
  def c(list1:List[A], list2:List[A]): Int = {
    (list1, list2) match {
      case (Nil, Nil) => 0
      case (x::xs, Nil) => 1
      case (Nil, y::ys) => -1
      case (x::xs, y::ys) => (x compare y) match {
        case 0 => c(xs, ys)
        case i => i
      }
    }
  }
  new Ordered[List[A]] {
    def compare(list2: List[A]): Int = c(list1, list2)
  }
}

关于评论：我曾经认为这是一个品味问题。有时，验证递归功能的正确性更容易，当然您的版本足够短，没有令人信服的理由更喜欢递归。

不过，我对性能的影响很感兴趣。所以我试图对其进行基准测试：查看 http://gist.github.com/468435. 。我很惊讶地看到递归版本更快（假设我正确地进行了基准）。结果仍然适用于大约长度10的列表。