Scala context bound unexpectedly not working

Question

I tried to define a function that would check whether a generic Seq is sorted.

I came up with this:

import Ordering.Implicits._

def isOrdered[A: Ordering](seq: Seq[A]): Boolean =
  seq.sliding(2).map({ case List(a, b) => b > a }).forall(identity)

At which point, the compiler throws back "No implicit Ordering defined for A".

I can work around this by ascribing a and b as follows:

def isOrdered[A: Ordering](seq: Seq[A]): Boolean =
  seq.sliding(2).map({ case List(a: A, b: A) => a < b }).forall(identity)

At which point the compiler happily accepts the function.

What I find curious is that the following implementation works out of the box:

def isOrdered[A: Ordering](seq: Seq[A]): Boolean =
  seq.sliding(2).exists{s => s(0) > s(1)}

Where as far as I can tell, the only significant difference is that I don't use a partial function.

Can anyone explain this behavior?

Answer 1

In the first case,

{ case List(a, b) => b > a }

This doesn't work because you have just defined a partial function but not the Ordering of those elements. In the sense case List(a,b) represents a List containing a and b. Now a can mean anything. Doing a:A, b:A works because now you define that it is a List containing 2 elements of type A.

And because we have defined Ordering for A. Hence the second works.

As per the third one: seq.sliding(2). returns a Iterator[List[A]]. For each List[A] in the iterator, you are calling s(0) > s(1). Here s(0) and s(1) is of type A. Because you have defined the bound A: Ordering, you have ordering defined for type A. In this case s(0) s(1). Hence it works.

Answer 2

The accepted answer is pretty unsatisfying to me, in the sense that I still don't know what's going on.

My first reaction is, It must a bug with implicits + inference, whether it's something they know about yet or not.

The problem doesn't reside in, say, the type param for map, since it reduces to the match:

scala> def f[X: Ordering](seq: Seq[X]) = seq match { case List(a,b) => b > a }

How can that not work? My speculation is that it will have to do with the invariance of Ordered, so that the way List.unapply is unpacked is compared to the input Seq means we can't rely on the implicit Ordering in scope.

Let's turn on some debug. (-Xprint:typer,patmat, -Xlog-implicits, -Yinfer-debug)

This is how the case Seq is translated at typer:

def f[A](seq: Seq[A])(implicit evidence$1: Ordering[A]): Boolean = seq match {
  case collection.this.Seq.unapplySeq[A](<unapply-selector>) <unapply> ((a @ _), (b @ _)) => scala.`package`.Ordering.Implicits.infixOrderingOps[A](b)(evidence$1).>(a)

and at patmat:

def f[A](seq: Seq[A])(implicit evidence$1: Ordering[A]): Boolean = {
  case <synthetic> val x1: Seq[A] = seq;
  case5(){
    <synthetic> val o7: Option[Seq[A]] = collection.this.Seq.unapplySeq[A](x1);
    if (o7.isEmpty.unary_!)
      if (o7.get.!=(null).&&(o7.get.lengthCompare(2).==(0)))
        {
          val a: A = o7.get.apply(0);
          val b: A = o7.get.apply(1);
          matchEnd4(scala.`package`.Ordering.Implicits.infixOrderingOps[A](b)(evidence$1).>(a))
        }
      else
        case6()
    else
      case6()
  };

In other words, the unapply just gives back your Seq, and it gets the first two elements.

The case List should look exactly the same, except it doesn't type check.

OK, I got distracted by other things, like my daughter started swimming underwater today, so to short-circuit, this works:

scala> import Ordering.Implicits.infixOrderingOps
import Ordering.Implicits.infixOrderingOps

scala> import reflect.ClassTag
import reflect.ClassTag

scala> def f[X](seq: Seq[X])(implicit e1: Ordering[X], e2: ClassTag[X]) = seq match { case xs: List[X] if xs.length == 2 => xs(1) > xs(0) }
f: [X](seq: Seq[X])(implicit e1: Ordering[X], implicit e2: scala.reflect.ClassTag[X])Boolean

Maybe this deficit is at play.