Ordering

Ordering in Scala

Ordering in scala implemended with following types located at scala.math:

• Ordering[T] - trait whose instances each represent a strategy for sorting instances of a type.

• PartialOrdering[T] - representation of partial ordering on some type.

• Equiv[T] - representation of equivalence on some type.

• Ordered[T] - trait for data that have a single, natural ordering.

• Ordering.Implicits - access to other implicit orderings.

Ordering

Ordering is a trait whose instances each represent a strategy for sorting instances of a type. An Ordering[T] is implemented by specifying compare(a:T, b:T), which decides how to order two instances a and b. Ordering has the same purpose as Comparator in Java, but with scala extensions, implicit and related math properties.

Most sorting functionality implemented in the scala library operates using instances of Ordering, so usage of sorting is a preferable way to implement order relation in scala. Providing an ordering directly eliminates an implicit conversion in most cases.

Instances of Ordering[T] can be used by things like scala.util.Sorting to sort collections like Array[T].

import scala.util.Sorting

case class Person(name:String, age:Int)
val people = Array(Person("bob", 30), Person("ann", 32), Person("carl", 19))

// sort by age
object AgeOrdering extends Ordering[Person] {
  def compare(a:Person, b:Person) = a.age compare b.age
}
Sorting.quickSort(people)(AgeOrdering)

Ordering companion object

Ordering's companion object defines many implicit objects to deal with subtypes of AnyVal (e.g. Int, Double), String, and others.

• Ordering.by

• Ordering.on

case class Employee(id: Int, firstName: String, lastName: String)

object Employee {
  // Note that because `Ordering[A]` is not contravariant, the declaration
  // must be type-parametrized in the event that you want the implicit
  // ordering to apply to subclasses of `Employee`.
  implicit def orderingByName[A <: Employee]: Ordering[A] =
    Ordering.by(e => (e.lastName, e.firstName))

  val orderingById: Ordering[Employee] = Ordering.by(e => e.id)
}

Given es: SeqLike[Employee], es.sorted() will sort by name, and es.sorted(Employee.orderingById) will sort by id.

For case classes ordering on deconstruction can be used:

object A {
  implicit val ord = Ordering.by(unapply)
}

This has the benefit that it is updated automatically whenever A changes. But, A's fields need to be placed in the order by which the ordering will use them.

Ordered

Trait Ordered is the analogue of Comparable in Java. Classes that implement Ordered trait can be sorted with scala.util.Sorting and can be compared with standard comparison operators (e.g. > and <). Ordered and Ordering both provide implicits allowing them to be used interchangeably.

case class A(tag: String, load: Int) extends Ordered[A] {
  // Required as of Scala 2.11 for reasons unknown - the companion to Ordered
  // should already be in implicit scope
  import scala.math.Ordered.orderingToOrdered

  def compare(that: A): Int = (this.tag, this.load) compare (that.tag, that.load)
}

Note that Ordering and Ordered does not provide implementation of equals methods. Developers must implement this method by itself and make sure that it consistent with ordering.

Extra Implicits

This works: why??

import scala.math.Ordering.Implicits._
var x = (1,2,3) < (1,2,4)

Partial Ordering

Partial Ordering trait defines only one method def lteq(x: T, y: T): Boolean which returns true iff x comes before y in the ordering.

A partial ordering is a binary relation on a type T, exposed as the lteq method of this trait. This relation must be: reflexive: lteq(x, x) == true, for any x of type T. anti-symmetric: if lteq(x, y) == true and lteq(y, x) == true then equiv(x, y) == true, for any x and y of type T. transitive: if lteq(x, y) == true and lteq(y, z) == true then lteq(x, z) == true, for any x, y, and z of type T.

Additionally, a partial ordering induces an equivalence relation on a type T: x and y of type T are equivalent if and only if lteq(x, y) && lteq(y, x) == true.

Equivalence relation

An equivalence relation is a binary relation on a type. This relation is exposed as the equiv method of the Equiv trait. The relation must be: reflexive: equiv(x, x) == true for any x of type T. symmetric: equiv(x, y) == equiv(y, x) for any x and y of type T. transitive: if equiv(x, y) == true and equiv(y, z) == true, then equiv(x, z) == true for any x, y, and zs of type T.

Sorting in Scala

Sorting in scala implemented in scala.util.Sorting object.

Вопросы:

• Какие типы отвечают за упорядочивание в scala?

• Как работает trait Ordering, какие у него возможности.

• Способы применения Ordering.

• В чем отличие Ordered от Ordering.

• Как подключить реализованные неявные Ordering для разных типов данных?

• Как задать частичный порядок на типе T?

• Какие свойства частичного порядка есть?

• Как задать отношение эквивалентности на типе T. Какими свойствами должно обладать отношение эквивалентности.

• Как реализована сортировка в Scala.