Returning an Ordered[T] from a method in Scala

Question

I have a simple trait that requires the implementation to have a method quality(x:A) which I want to return an Ordered[B]. In other words, quality transforms A to Ordered[B]. Such that I can compare to B's.

I have the following basic code:

trait Foo[A] {
    def quality[B](x:A):Ordered[B]

    def baz(x1:A, x2:A) = {
       // some algorithm work here, and then
       if (quality(x1) > quality(x2)) {
           // some stuff
       }
}

Which I want to implement like follows:

class FooImpl extends Foo[Bar] {
    def quality(x:Bar):Double = {
       someDifficultQualityCalculationWhichReturnsADouble
    }
}

I figured this could work because Double is implicitly converted to RichDouble which implements Ordered[Double] if I am correct.
But at the > in the baz method of the trait it gives me an error of quality(x2) stating: Type mismatch, expected Nothing, actual Ordered[Nothing]

I do not understand this, because, coming from C#, I find it comparable to returning something like IEnumerable<A> and then using al the nice extension methods of an IEnumerable.

What am I missing here? What I want to to with the trait is define a complex algorithm inside the trait, but the key functions need to be defined by the class implementing the trait. On of these functions is needed to calculate a quality factor. This can be a Double, Int or whatnot but it can also be something more sophisticated. I could rewrite it that it always returns Double and that is certainly possible, but I want the trait to be as generic as possible because I want it to describe behavior and not implementation. I thought about the class A implementing Ordered[A] but that also seems weird, because it is not the 'purpose' of this class to be compared.

Answer 1

To complement Peter's answer: in Scala we have two traits: Ordering[T] and Ordered[A]. You should use them in different situations.

Ordered[A] is for cases when a class you implement can be ordered naturally and that order is the only one.

Example:

class Fraction(val numerator: Int, val denominator: Int) extends Ordered[Fraction]
{
  def compare(that: Fraction) = {
    (this.numerator * that.denominator) compare (this.denominator * that.numerator)
  }
}

Ordering[T] is for cases when you want to have different ways to order things. This way the strategy of defining the order can be decoupled from the class being ordered.

For an example I will borrow Peter's Person:

case class Person(name: String, age: Int)

object PersonNameOrdering extends Ordering[Person]
{
  def compare(x: Person, y: Person) = x.name compare y.name
}

Note, that since PersonNameOrdering doesn't have any instance fields, all it does is encapsulate the logic of defining an order of two Person's. Thus I made it an object rather than a class.

To cut down the boilerplate you can use Ordering.on to define an Ordering:

val personAgeOrdering: Ordering[Person] = Ordering.on[Person](_.age)

---

Now to the fun part: how to use all this stuff.

In your original code Foo[A].quantity was indirectly defining a way to order your A's. Now to make it idiomatic Scala let's use Ordering[A] instead, and rename quantity to ord:

trait Foo[A] {
  def baz(x1: A, x2: A, ord: Ordering[A]) = {
    import ord._
    if (x1 > x2) "first is greater"
    else "first is less or equal"
  }
}

Several things to note here:

• import ord._ allows to use infix notation for comparisons, i.e. x1 > x2 vs ord.gt(x1, x2)

• baz is now parametrized by ordering, so you can dynamically choose how to order x1 and x2 on a case-by-case basis:

  foo.baz(person1, person2, PersonNameOrdering)
  foo.baz(person1, person2, personAgeOrdering)
  

The fact that ord is now an explicit parameter can sometimes be inconvenient: you may not want to pass it explicitly all the time, while there might be some cases when you want to do so. Implicits to the rescue!

def baz(x1: A, x2: A) = {
  def inner(implicit ord: Ordering[A]) = {
    import ord._
    if (x1 > x2) "first is greater"
    else "first is less or equal"
  }
  inner
}

Note the implicit keyword. It is used to tell the compiler to draw the parameter from the implicit scope in case you don't provide it explicitly:

// put an Int value to the implicit scope
implicit val myInt: Int = 5

def printAnInt(implicit x: Int) = { println(x) }
// explicitly pass the parameter
printAnInt(10) // would print "10"

// let the compiler infer the parameter from the implicit scope
printAnInt // would print "5"

You might want to learn where does Scala look for implicits.

Another thing to note is the need of a nested function. You cannot write def baz(x1: A, x2: A, implicit ord: Ordering[A]) - that would not compile, because the implicit keyword applies to the whole parameter list.

In order to cope with this little problem baz was rewritten in such a clunky way.

This form of rewritting turned out to be so common that a nice syntactic sugar was introduced for it - multiple parameter list:

def baz(x1: A, x2: A)(implicit ord: Ordering[A]) = {
  import ord._
  if (x1 > x2) "first is greater"
  else "first is less or equal"
}

The need of an implicit parametrized by a type is also quite common so the code above can be rewritten with even more sugar - context bound:

def baz[A: Ordering](x1: A, x2: A) = {
  val ord = implicitly[Ordering[A]]
  import ord._
  if (x1 > x2) "first is greater"
  else "first is less or equal"
}

Please bear in mind that all these transformations of baz function are nothing but syntactic sugar application. So all the versions are exactly the same and compiler would desugarize each of the versions to the same bytecode.

---

To recap:

1. extract the A ordering logic from quantity function to the Ordering[A] class;
2. put an instance of Ordering[A] to the implicit scope or pass the ordering explicitly depending on your needs;
3. pick "your flavor" of syntactic sugar for baz: no sugar/nested functions, multiple parameter list or context bound.

---

UPD

To answer the original question "why doesn't it compile?" let me start from a little digression on how infix comparison operator works in Scala.

Given the following code:

val x: Int = 1
val y: Int = 2
val greater: Boolean = x > y

Here's what actually happens. Scala doesn't have infix operators per se, instead infix operators are just a syntactic sugar for single parameter method invocation. So internally the code above transforms to this:

val greater: Boolean = x.>(y)

Now the tricky part: Int doesn't have an > method on its own. Pick ordering by inheritance on the ScalaDoc page and check that this method is listed in a group titled "Inherited by implicit conversion intWrapper from Int to RichInt".

So internally compiler does this (well, except that for performance reasons that there is no actual instantiation of an extra object on heap):

val greater: Boolean = (new RichInt(x)).>(y)

If we proceed to ScalaDoc of RichInt and again order methods by inheritance it turns out that the > method actually comes from Ordered!

Let's rewrite the whole block to make it clearer what actually happens:

val x: Int = 1
val y: Int = 2
val richX: RichInt = new RichInt(x)
val xOrdered: Ordered[Int] = richX
val greater: Boolean = xOrdered.>(y)

The rewriting should have highlighted the types of variables involved in comparison: Ordered[Int] on the left and Int on the right. Refer > documentation for confirmation.

Now let's get back to the original code and rewrite it the same way to highlight the types:

trait Foo[A] {
    def quality[B](x: A): Ordered[B]

    def baz(x1: A, x2: A) = {
       // some algorithm work here, and then
       val x1Ordered: Ordered[B] = quality(x1)
       val x2Ordered: Ordered[B] = quality(x2)

       if (x1Ordered > x2Ordered) {
           // some stuff
       }
    }
}

As you can see the types do not align: they are Ordered[B] and Ordered[B], while for > comparison to work they should have been Ordered[B] and B respectively.

The question is where do you get this B to put on the right? To me it seems that B is in fact the same as A in this context. Here's what I came up with:

trait Foo[A] {
  def quality(x: A): Ordered[A]

  def baz(x1: A, x2: A) = {
    // some algorithm work here, and then
    if (quality(x1) > x2) {
      "x1 is greater"
    } else {
      "x1 is less or equal"
    }
  }
}

case class Cargo(weight: Int)

class CargoFooImpl extends Foo[Cargo] {
  override def quality(x: Cargo): Ordered[Cargo] = new Ordered[Cargo] {
    override def compare(that: Cargo): Int = x.weight compare that.weight
  }
}

The downside of this approach is that it is not obvious: the implementation of quality is too verbose and quality(x1) > x2 is not symmetrical.

---

The bottom line:

• if you want the code to be idiomatic Scala go for Ordering[T]
• if you don't want to mess with implicits and other Scala magic implement quality as quality(x: A): Double for all As; Doubles are good and generic enough to be compared and ordered.

Answer 2

Using Ordering[A] you can compare As without requiring A to implement Ordered[A].

We can request that an Ordering[A] exists in baz by adding an implicit parameter :

trait Foo[A] {
  def baz(x1:A, x2:A)(implicit ord: Ordering[A]) = 
   if (ord.gt(x1, x2)) "first is bigger"
   else "first is smaller or equal"
}

Lets create a Person case class with an Ordering in its companion object.

case class Person(name: String, age: Int)
object Person {
  implicit val orderByAge = Ordering.by[Person, Int](_.age)
}

We can now use Foo[Person].baz because an Ordering[Person] exists :

val (alice, bob) = (Person("Alice", 50), Person("Bob", 40))

val foo = new Foo[Person] {}
foo.baz(alice, bob)
// String = first is bigger

// using an explicit ordering 
foor.baz(alice, bob)(Ordering.by[Person, String](_.name))
// String = first is smaller or equal

In the same manner as I compared Persons by age, you could create an Ordering[A] to compare your A by your quality function.