Подтвердить что ты не робот

Как scala упорядочивает кортежи?

Я пытаюсь понять, как scala обрабатывает упорядочение и сортировку кортежей

Например, если я получил список

val l = for {i <- 1 to 5} yield (-i,i*2)
Vector((-1,2), (-2,4), (-3,6), (-4,8), (-5,10))

scala знает, как его сортировать:

l.sorted
Vector((-5,10), (-4,8), (-3,6), (-2,4), (-1,2))

Но кортеж не имеет '<' Метод:

l.sortWith(_ < _)

error: value < is not a member of (Int, Int)
l.sortWith(_ < _)

Как scala знать, как сортировать эти кортежи?

Ответ 1

Потому что sorted имеет неявный параметр ord:

def sorted [B > : A] (implicit ord: math.Ordering [B]): Список [A] Сортировка эта последовательность в соответствии с порядком.

Сорт стабилен. То есть, элементы, которые равны (как определено lt) отображаются в том же порядке в отсортированной последовательности, что и в оригинал.

ord порядок, используемый для сравнения элементов.

и существует неявное преобразование, определенное в scala.math.Ordering:

implicit def Tuple2[T1, T2](implicit ord1: Ordering[T1], 
                                     ord2: Ordering[T2]): Ordering[(T1, T2)]

Итак, l.sorted будет преобразовано в l.sorted(scala.math.Ordering.Tuple2[Int, Int]()).

Проверьте это:

scala> def catchOrd[A](xs: A)(implicit ord: math.Ordering[A]) = ord
catchOrd: [A](xs: A)(implicit ord: scala.math.Ordering[A])scala.math.Ordering[A]

scala> catchOrd((1,2))
res1: scala.math.Ordering[(Int, Int)] = [email protected]

И, конечно же, вы можете определить свой собственный Ordering:

scala> implicit object IntTupleOrd extends math.Ordering[(Int, Int)] {
     |   def compare(x: (Int, Int), y: (Int, Int)): Int = {
     |     println(s"Hi, I am here with x: $x, y: $y")
     |     val a = x._1*x._2
     |     val b = y._1*y._2
     |     if(a > b) 1 else if(a < b) -1 else 0
     |   }
     | }
defined object IntTupleOrd

scala> Seq((1, 10), (3, 4),  (2, 3)).sorted
Hi, I am here with x: (1,10), y: (3,4)
Hi, I am here with x: (3,4), y: (2,3)
Hi, I am here with x: (1,10), y: (2,3)
res2: Seq[(Int, Int)] = List((2,3), (1,10), (3,4))

EDIT Существует короткий способ сделать Tuple[Int, Int] поддержку всех следующих методов: <, <=, >, >=.

scala> implicit def mkOps[A](x: A)(implicit ord: math.Ordering[A]): ord.Ops =
     |   ord.mkOrderingOps(x)
mkOps: [A](x: A)(implicit ord: scala.math.Ordering[A])ord.Ops

scala> (1, 2) < (3, 4)
res0: Boolean = true

scala> (1, 2) <= (3, 4)
res1: Boolean = true

scala> (1, 2, 3) <= (1, 2, 4)
res2: Boolean = true

scala> (3, 3, 3, 3) >= (3, 3, 3, 4)
res3: Boolean = false

Ответ 2

@Eastsun ответ прекрасно объясняет первую часть вашего вопроса "как Scala сортировать кортежи".

Что касается второй части, "почему кортеж не имеет метода <": в Scala компараторы, такие как <, переводят на собственные сравнения JVM для базовых типов (при сравнении Int или Double и т.д.) или к функциям-членам someClass с типом <(that: someClass): Boolean. Этот случай на самом деле просто синтаксический сахар: someObject < otherObject переводится на someObject.<(otherObject). Если вы хотите иметь эту функцию для кортежей, вы можете ввести неявный класс в область видимости и сопоставить функцию-член сравнения с компараторами, предоставленными Ordering:

implicit class ProvideComparator[T](t1: T)(implicit ord: Ordering[T]) {
  def <(t2: T) = ord.lt(t1, t2)
  def >(t2: T) = ord.gt(t1, t2) // and so on
}

Теперь вы можете просто написать:

scala> (1,2) < (2,2)
res2: Boolean = true