Reverse String ordering

Question
1

scala.math.Ordering

trait StringOrdering extends Ordering[String] {
        def compare(x: String, y: String) = x.compareTo(y)
}
implicit object String extends StringOrdering

I wish to have an ordering on strings that is opposite to the ordering above. I could define a new ordering:

trait ReverseStringOrdering where def compare is y.compareTo(x).

However, it maybe neater to reuse the existing code by using the .reverse on the above ordering. However I’m not sure how to implement this.

Something like

object ReverseStringOrdering extends StringOrdering.reverse
or object ReverseStringOrdering extends Ordering[String].reverse?

It says StringOrdering is not a member of scala.math.Ordering.

2

The #reverse invocation will give you an object instance - you cannot extend this.

The simplest way:

implicit val revOrd: Ordering[String] = Ordering.String.reverse

Note that you can’t do

implicit val revOrd: Ordering[String] =
  implicitly[Ordering[String]].reverse // NullPointerException

…because it will prematurely look up itself in the implicitly application. If you need something like this, you’ll have to scope it (unless there’s a better way I’m not aware of), e.g.

val strOrd: Ordering[String] = implicitly[Ordering[String]]

{
  implicit val revOrd: Ordering[String] = strOrd.reverse
  // ...
}

If you insist on having an object/trait/class for this reverse ordering, you’ll have to explicitly implement it, e.g.

implicit object RevStringOrdering extends Ordering[String] {
  override def compare(x: String, y: String): Int =
    Ordering.String.reverse.compare(x, y)
}
2 Likes
3

Yes - this last line is great. I’m putting off using Implicits for now so I keep my head around everything - even if I have to add the Sorting object each time sorted is called.

Another challenge would be given tuples of types which have may have explicit Ordering objects, what is the best way of making the standard library do it?

Eg. val mylist: List[(A,Int)] = (MyA("a"), 1) :: (MyB("a"), 4) :: Nil then mylist.sorted

The scala.math.Ordering says Iterable’s Orderings are unsafe so use Seq’s ordering in an ExtraImplicit object which adds an extra level of confusion.

But basically I would like something (with minimal implicits) like

mylist.sorted(Tuple2Ordering(MyAOrderingobject, scalasinbuiltIntOrdering))

and more also

mylist1 < mylist2

where the lists are the list of tuples?

A bit hard to express!

4

Well, with implicits:

case class MyA(s: String)

implicit val myAOrdering: Ordering[MyA] = Ordering.by(_.s)
import Ordering.Implicits._

val a = Seq(MyA("a") -> 1, MyA("b") -> 2)
val b = Seq(MyA("b") -> 2, MyA("c") -> 3)

println(a < b)

With explicit ordering declarations, the last line becomes something like

println(infixOrderingOps(a)(seqOrdering(Ordering.Tuple2(myAOrdering, Ordering.Int))) < b)

(Probably your IDE has a feature to help “unrolling” implicits like this - IntelliJ IDEA does.)

I’m not sure this latter style would help me to keep my head around everything… :wink:

5

Thanks so much! This is really useful.

Finally, do you know why Iterable Orderings are unsafe (aren’t these in implicit scope by default)? If so, do we need to remember to use seqOrdering each time? E.g. if I just tried to sort a list using sorted I should be safe, or do I need to worry? Or do Seq’s override the in scope implicit with their own?

6

Iterables aren’t guaranteed to iterate in the same order each time you iterate over them. An ordering over an iterable needs to be OK with that.

7

I have no idea about the exact shape of the underlying issue (and I’m not inclined to investigate, there may be dragons :wink:). However, the doc for #seqOrdering says that its presence in scope may induce diverging expansions, i.e. a potentially infinite, recursive chain of implicit resolutions. It provides the, somewhat silly, example of implicitly[Ordering[Any]], and indeed, this combination triggers the corresponding compiler error.

I wouldn’t worry about it that much. Only bring those extra implicits in scope where you need them, and if the compiler happens to complain in some scenario, you’ll still have ample time to ponder over it. :smirk: I would expect these instances to be rather rare. (But then, I’d expect the need to order Seqs to be rare, as well.)

Generic Iterable orderings, on the other hand, have been deprecated for the reason @martijnhoekstra mentioned.

#seqOrdering is only required for imposing an order on Seq instances, not for the order of Seq elements, as required when sorting a Seq.