1

Is there any way, given an object with the trait Ordered, to get an Ordering which uses the same comparison as the original object?

The reason I want to do this is I have implemented a merge sort with the following signature (the Manifests are just so that I can instantiate new List[T]s and Array[T]s:

def mergeSorted[T : Manifest](li: List[T], ord: Ordering[T]) : List[T]

What I want to do is overload this with a method with this signature:

def mergeSorted[T <: Ordered[T] : Manifest](li: List[T]) : List[T]

This way, I wouldn't have to manually, say, put in the Int ordering if I were sorting Ints. It seems to me that the easies way to implement this would just be to get an Ordering[T] from T somehow. The ScalaDoc seems to say that this is possible through implicits:

Ordered and Ordering both provide implicits allowing them to be used interchangeably.

However, I don't know which implicits to import in order to do this.

ostrichofevil
  • 749
  • 7
  • 19

2 Answers2

1

Both math.Ordering and math.Ordered can achieve what you need by means of implicit parameter and implicit conversion, respectively. Depending on which one to use, the mergeSort function will have a signature similar to one of the following:

// Using math.Ordering
def mergeSort[T](li: List[T])(implicit order: Ordering[T]): List[T] = {
  ...
}

// Using math.Ordered
def mergeSort[T <% Ordered[T]](li: List[T]): List[T] = {
  ...
}

For details, this generic merge sort blog post might be of interest to you.

Leo C
  • 22,006
  • 3
  • 26
  • 39
  • 1
    Your comment (and blog post) is good, @Leo C, but you should point out that, in the first case, it would be more elegant to use a "context bound" (aka Type Class): `// Using math.Ordering def mergeSort[T : Ordering](li: List[T]): List[T] = { ... }` – Phasmid Apr 16 '17 at 17:11
  • @Phasmid, For completeness I agree with you – although I was even thinking, in the `math.Ordered` case, just stopping at the raw `def mergeSort[T](li: List[T])(implicit orderer: T => Ordered[T]): List[T] = { ... }`. Sometimes Scala's abundance of syntactic sugars aren't helping too much those who are still learning the essence of the language. – Leo C Apr 16 '17 at 18:10
  • Very useful blog post; it showed how the implicits work behind the scenes. (I accepted the other answer because it was the one that ended up working well for my code.) It's honestly kind of funny how similar the problem addressed by that post is to my own. – ostrichofevil Apr 17 '17 at 11:26
  • Glad that it helps. – Leo C Apr 17 '17 at 15:32
1

If you define:

def mergeSorted[T : Ordering : Manifest](li: List[T]) : List[T]

the compiler will desugar that into

def mergeSorted[T : Manifest](li: List[T])(implicit ev: Ordering[T]) : List[T]

and everything will work just as you want.

Phasmid
  • 923
  • 7
  • 19