如何在Scala中按未知数量的项目对列表进行排序？

Question

我看过这个问题如何通过两个字段对Scala中的列表进行排序？

这类似但不是重复。

我可以轻松地使用早期问题的答案来对List [DataPoint]进行排序：

case class DataPoint(keys: List[String], value: Double)

listOfDataPoints.sortBy(point => (point.keys(0), point.keys(1)))

然而我不知道keys中项的数量。我所知道的是，给定列表中的每个DataPoint将具有相同的键数，因此永远不会出现对List("a")和List("a", "b")进行排序的情况。

那么我如何按未知数量的键排序列表？

- jimmy_terra

---

List("a")和List("a", "b")按什么顺序排序？ - Martijn

添加了一个澄清。 - jimmy_terra

Answer 1

你想要做的是：

datapoints.sortby(_.keys)

这显然是行不通的。当我们看一下"sortby"的签名时，就会变得很明显为什么它不能工作:

sortBy[B](f: (A) ⇒ B)(implicit ord: math.Ordering[B]): List[A]

您的B是一个List[String]，而且您没有Ordering[List[String]]的实例。那么我们该怎么办呢？我们提供一个！

为此，我们需要实现该方法：

def compare(x: T, y: T): Int

我们希望按照以下方式进行比较：

• 如果两个项之间的第一个键不同，则使用该键进行排序
• 否则，按列表的其余部分进行排序
• 如果其中一个列表为空，则另一个列表排在前面^[1]

我们这里的T是字符串，但是对于T来说，我们只需要可比较性，所以我们可以更加通用。

def listOrdering[T](implicit ord: Ordering[T]): Ordering[List[T]] = new Ordering[List[T]] {
  def compare(x: List[T], y: List[T]): Int = {
    (x, y) match {
      case (Nil, Nil) => 0 //both empty => equal
      case (Nil, _)   => -1 //one of the two empty => empty is the smallest
      case (_, Nil)   => 1 //one of the two empty => empty is the smallest
      case (xhead :: xtail, yhead :: ytail) => {
        val headdiff = ord.compare(xhead, yhead)
        if (headdiff == 0) compare(xtail, ytail) //recursively compare the tails if equivalent
        else (headdiff ) //otherwise, the difference in the heads
      }  
    }
  }
}

现在我们可以明确地向sortby方法提供排序方式：

datapoints.sortby(_.keys)(listOrdering)

或者在隐式范围内提供它们。

[1]: 您表示这种情况从未发生，因此任何选择都足够好。

- Martijn

---

太棒了，看起来像是解决方案，我会尝试一下。 - jimmy_terra

作为一种评论，虽然我的实现旨在最大程度地解释，但@Shadowlands的实现更加简洁，对许多人来说可能更加自明。 - Martijn

Answer 2

你可以定义自己的Ordering[List[String]]。例如，你可以定义:

class ListOrdering[A](implicit aOrd: math.Ordering[A]) extends Ordering[List[A]] {    
  def compare(a1: List[A], a2: List[A]) = (a1, a2) match {
    case (Nil, _) => if (a2.isEmpty) 0 else -1
    case (_, Nil) => 1
    case (h1 :: t1, h2 :: t2) => if (aOrd.compare(h1, h2) == 0) compare(t1, t2) else aOrd.compare(h1, h2)
  }    
}

然后在某个范围内提供以下内容：

implicit val listOrd = new ListOrdering[String]

you can write:

dps.sortBy(_.keys)

希望它能够正常工作。

请注意，我的ListOrdering定义是泛化的，可用于任何类型A，在范围内有一个隐式Ordering[A]，并且可以处理可变长度的列表（即使您说在您的情况下，关键列表始终具有相同的长度）。

- Shadowlands

---

这意味着如果（h1！= h2），那么 compare(h1, h2) != 0，但这并非必然。 - Martijn