14

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

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

并得到列表按字典顺序排序的东西。当然，仅仅因为Ahas traitOrdered[A]并不意味着List[A]具有 trait Ordered[List[A]]。然而，据推测，执行此操作的“scala 方式”是使用隐式定义。

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

我想对对象使用字典排序List[A]，但我想要可以适应其他排序的代码。

4

6 回答 6

24

受到 Ben Lings 回答的启发，我设法找出了按字典顺序对列表进行排序的最简单方法：添加行

import scala.math.Ordering.Implicits._

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

于 2011-03-30T18:57:48.693 回答
6

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

这里要注意的重要一点是 ' view bound ' A <% Ordered[A]，它确保它A本身不需要 an Ordered[A]，只是有一种方法可以进行这种转换。令人高兴的是，Scala 库的对象Predef具有从Ints 到RichInts 的隐式转换，尤其是Ordered[Int]s。

其余的代码只是实现字典排序。

于 2010-06-29T05:01:23.317 回答
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].

于 2010-06-29T11:55:57.107 回答
4

受 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
}
于 2011-03-31T00:51:39.767 回答
3

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

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 的列表。

于 2010-06-30T06:39:18.737 回答
1

仅仅因为我已经以另一种方式实现了这一点，所以这里有一个不使用的非递归版本return：

new Ordering[Seq[String]]() {
  override def compare(x: Seq[String], y: Seq[String]): Int = {
    x.zip(y).foldLeft(None: Option[Int]){ case (r, (v, w)) =>
        if(r.isDefined){
          r
        } else {
          val comp = v.compareTo(w)
          if(comp == 0) None
          else Some(comp)
        }
      }.getOrElse(x.size.compareTo(y.size))
    }
  }
于 2019-10-17T07:34:51.640 回答