Implicit conversion from Comparator to Ordering

Question
1

What is the reason this doesn’t work:

import Ordering.comparatorToOrdering

val strings: List[String] = ...
strings.sorted(String.CASE_INSENSITIVE_ORDER)

Note that strings.sorted(comparatorToOrdering(String.CASE_INSENSITIVE_ORDER)) does work, and that comparatorToOrdering is an implicit def.

Addendum:
I must be having a Scala bad day. This program:

object Test {
  implicit val caseInsensitive: Ordering[String] = Ordering.by(_.toLowerCase)
  val strings: List[String] = List("a", "C", "b")
  
  def main(args: Array[String]) = {
    println(strings.sorted)
  }
}

crashes with an NPE:

java.lang.NullPointerException
	at scala.math.Ordering$$anon$5.compare(Ordering.scala:329)
	at java.base/java.util.TimSort.countRunAndMakeAscending(TimSort.java:355)
	at java.base/java.util.TimSort.sort(TimSort.java:220)
	at java.base/java.util.Arrays.sort(Arrays.java:1232)
	at scala.collection.SeqOps.sorted(Seq.scala:705)
	at scala.collection.SeqOps.sorted$(Seq.scala:697)
...
2

A couple of things here, so let’s go step by step.

For your first example, if you take a look to the Scaladoc you will see that comparatorToOrdering expects an implicit Comparator so that is why it doesn’t work.

We may try this:

implicit val cmp = String.CASE_INSENSITIVE_ORDER
strings.sorted

However, this will still use the normal Ordering[String] because it has higher precedence.
So we need to make something like this:

// No need to import Ordering.comparatorToOrdering since it is already in scope.
def test[A](data: List[A])(implicit cmp: java.util.Comparator[A]): List[A] = data.sorted

test(List("a", "C", "b"))(String.CASE_INSENSITIVE_ORDER)
// res: List[String] = List(a, b, C)

Now about your second example, the problem is very simple. As the Scaladoc mentions, by expects function from an T => S and an implicit Ordering[S] to return a Ordering[T].
So, in this case, the function is a String => String so this needs an implicit Ordering[String] to return an Ordering[String], which makes sense… but, in this case the result is assigned to an implicit val of type Ordering[String] so the compiler uses caseInsensitive to create caseInsensitive which results in a loop that ends up in the NPE you are seeing.

There are two ways to solve this:

// Option 1 - Making and using caseInsensitive explicitly
val caseInsensitive: Ordering[String] = Ordering.by(_.toLowerCase)
strings.sorted(caseInsensitive)

// Option 2 - Using on instead of by
implicit val caseInsensitive: Ordering[String] = Ordering.String.on(_.toLowerCase)
strings.sorted

However all this is extremely complicated and you can just:

val strings: List[String] = List("a", "C", "b")

strings.sortBy(_.toLowerCase)
// res: List[String] = List(a, b, C)
3

Thank you for the info.

Why is that? An implicit def with an implicit argument cannot be used on explicit arguments? It will only be triggered on implicit values? In general, methods declared with an implicit argument can still be called on an explicit argument.

Indeed, having:

implicit def conv(cmp: java.util.Comparator[String]): Ordering[String] =
  Ordering.comparatorToOrdering(cmp)

makes the call sorted(String.CASE_INSENSITIVE_ORDER) work.

I thought about that, but I expected the definition of caseInsensitive to rely on implicits available before the definition is complete. But since vals can be defined recursively, it makes sense that the implicit argument of by ends up being null. Using a lazy val shows the infinite recursion you mention, instead of the NPE. I wish the compiler would force me to add lazy when a val is defined recursively. It would help see right away that the implicit argument to by is not the implicit already in scope, as I though it’d be.

I know. I was only trying to understand why it didn’t work (and I still don’t understand why the fact that the argument to comparatorToOrdering is implicit matters).

I can use:

implicit val caseInsensitive: Ordering[String] =
  (x: String, y: String) => x.compareToIgnoreCase(y)

to avoid the conversion to lowercase and thus get the equivalent of using CASE_INSENSITIVE_ORDER, but I was trying to rely on CASE_INSENSITIVE_ORDER directly instead.

4

Yeah, you can explicitly pass an implicit parameter (Scala 3 will make this even more explicit), but here you want to a non-implicit value to be picked for an implicit value, that doesn’t work never (and for good reasons).

Also, it is important to understand that there is a difference between implicit def foo(bar: Bar): Foo and implicit def foo(implicit bar: Bar): Foo, the first one is an implicit conversion from Bar to Foo, the second one is an inductive derivation of a Foo given a Bar (quite like logic programming) that why usually this version is parametrized on at least one type parameter.
Being honest, I would say that in this case, it should actually have been an implicit conversion, but there are probably reasons for it being an induction; but it would be good if someone that worked in the stdlib would complement on this.

Also, about the compiler picking a non-implicit value for an implicit argument would not only make the implicit resolution more complex and slower but also more fragile given there could be many possible values.

makes the call sorted(String.CASE_INSENSITIVE_ORDER) work.

Yeah because you used an implicit conversion, which as I said I also agree with you it would be better.

To be honest, I guess we all that have had this problem thought the same.
Not sure if Scala 3 improves on this? It is also questionable if there is any use case for a recursive implicit but knowing this community probably there is at least one.

If your value is lazy it can be recursive without the val being lazy, example:

val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map(n => n._1 + n._2)

I believe that since 2.13 there is a compiler flag that catches these errors, I do not remember which one it was though; since I am too used to sbt-tpolecat to turn all the useful flags for me.

Hope I helped with that :slight_smile:

You can also:

implicit val caseInsensitive: Ordering[String] = Ordering.fromLessThan {
  (x, y) => x.compareToIgnoreCase(y) < 0
}

Yeah, I guess you either have to be completely explicit about this or use your own implicit conversion as you did.

5

My Prolog is very rusted (though my predicate calculus is not). What’s the difference between a conversion and a derivation here? It looks like the second form will only convert an implicit value into another implicit value.

6

Practically speaking yes. On a more theorical? level, is the intention.

implicit def foo(bar: Bar): Foo

Means I can transform any instance of Bar into an instance of Foo.
This also means the way the feature is used, the compiler will register this transformation and use it anywhere a Foo is expected but it finds a Bar. It won’t search for a Bar anywhere, such Bar must be there.

On the other hand:

// As I said before, it is more common to use this with at least one type parameter.
implicit def foo[A](implicit bar: Bar[A]): Foo[A]

Means I can create a Foo[A] given I already have a Bar[A].
In this case, the compiler will attempt to use this inductive step whenever it requires to create an implicit value of type Foo[A] and it won’t expect (and won’t use) any explicit value of type Bar[A] but it will rather search for an (the only one) implicit Bar[A] on the implicit scope at that point.
A common example would be.

// A.k.a Semigroup
trait Combiner[A] {
  def combine(a1: A, a2: A): A
}

object Combiner {
  implicit final val IntCombiner: Combiner[Int] = (i1, i2) => i1 + i2

  implicit def OptionCombiner[A](implicit aCombiner: Combiner[A]): Combiner[Option[A]] = {
    case (Some(a1), Some(a2)) => aCombiner(a1, a2)
    case (Some(a), None) => Some(a)
    case (None, Some(a)) => Some(a)
    case (None, None) => None
  }
}