Scala function that sorts a Seq using the mapping of a generic function

Question

I'm trying to write a function that maps a sequence S by a function F (I'll call it F(S)), zips the resulting values (F(S)) with S, and sorts the result by F(S), returning the sorted zipped values (I hope the code clears this up, it's difficult to put into text)

Here's my current code:

def sortByAndReturnZippedMetric[S,M<:Ordering[AnyVal]]( s:Seq[S], mapper:S=>M):Seq[(M,S)] =
s.map(mapper).zip(s).sortBy(_._1)

Scalac is complaining, though:

error: diverging implicit expansion for type scala.math.Ordering[M]
starting with method comparatorToOrdering in trait LowPriorityOrderingImplicits
s.map(mapper).zip(s).sortBy(_._1)

                               ^

I'd appreciate some pointers as to what might be wrong...

Answer 1

Ordering is a type class, which means that if you want to capture the fact that A is ordered in a particular way, you simply put an implicit instance of Ordering[A] into scope—you don't have A extend Ordering[A] (or Ordering[AnyVal], etc.).

The advantage of this approach is that you can work with multiple orderings for a particular type (although only one implicit ordering can be in scope at a time for a type). So for example I can write the following:

scala> List(5, 2, 3, 1, 4).sorted
res0: List[Int] = List(1, 2, 3, 4, 5)

Here the implicit ordering for integers (Ordering.Int) is used as the implicit argument to sorted, but we could also explicitly pass a different Ordering. For example, we could create a new ordering by reversing the implicit one:

scala> List(5, 2, 3, 1, 4).sorted(Ordering.Int.reverse)
res1: List[Int] = List(5, 4, 3, 2, 1)

In your case sortBy is looking for an Ordering[Ordering[AnyVal]], which doesn't exist. You can easily fix this by using a context bound to indicate that you need an ordering for M, instead of having M extend Ordering[AnyVal]:

def sortByZipped[S, M: Ordering](s: Seq[S], mapper: S => M): Seq[(M, S)] =
  s.map(mapper).zip(s).sortBy(_._1)

Or you can skip the syntactic sugar and use an implicit argument:

def sortByZipped[S, M](s: Seq[S], mapper: S => M)(implicit o: Ordering[M]) =
  s.map(mapper).zip(s).sortBy(_._1)(o)

This is exactly equivalent to the version with the context bound.