How does the <:< operator work in Scala?

Question

In Scala there's a class <:< that witnesses a type constraint. From Predef.scala:

  sealed abstract class <:<[-From, +To] extends (From => To) with Serializable
  private[this] final val singleton_<:< = new <:<[Any,Any] { def apply(x: Any): Any = x }
  implicit def $conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

An example of how it's used is in the toMap method of TraversableOnce:

def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] =

What I don't understand is how this works. I understand that A <:< B is syntactically equivalent to the type <:<[A, B]. But I don't get how the compiler can find an implicit of that type if and only if A <: B. I assume that the asInstanceOf call in the definition of $conforms is making this possible somehow, but how? Also, is it significant that a singleton instance of an abstract class is used, instead of just using an object?

I'm aware that there are a couple of other questions about this class asking what it's for, or how to use it, but not how it works: https://stackoverflow.com/questions/2603003/ https://stackoverflow.com/questions/3427345/ And there's an exact duplicate of this question but it was itself closed as a duplicate, in my opinion erroneously- the question it's supposedly a duplicate *of* doesn't ask how the implementation *works*: https://stackoverflow.com/questions/11464976/ — Rag, Jun 02 '15 at 21:17
There's also http://stackoverflow.com/questions/21306623/scala-type-evidences/21306762#21306762 and http://stackoverflow.com/questions/22714609/using-scala-implicitly-for-type-equality/22717040#22717040 — Régis Jean-Gilles, Jun 03 '15 at 16:00

Travis Brown · Accepted Answer · 2015-06-02T22:01:54.590

Suppose we've got the following simple type hierarchy:

trait Foo
trait Bar extends Foo

We can ask for proof that Bar extends Foo:

val ev = implicitly[Bar <:< Foo]

If we run this in a console with -Xprint:typer, we'll see the following:

private[this] val ev: <:<[Bar,Foo] =
  scala.this.Predef.implicitly[<:<[Bar,Foo]](scala.this.Predef.$conforms[Bar]);

So the compiler has picked $conforms[Bar] as the implicit value we've asked for. Of course this value has type Bar <:< Bar, but because <:< is covariant in its second type parameter, this is a subtype of Bar <:< Foo, so it fits the bill.

(There's some magic involved here in the fact that the Scala compiler knows how to find subtypes of the type it's looking for, but it's a fairly generic mechanism and isn't too surprising in its behavior.)

Now suppose we ask for proof that Bar extends String:

val ev = implicitly[Bar <:< String]

If you turn on -Xlog-implicits, you'll see this:

<console>:9: $conforms is not a valid implicit value for <:<[Bar,String] because:
hasMatchingSymbol reported error: type mismatch;
 found   : <:<[Bar,Bar]
 required: <:<[Bar,String]
       val ev = implicitly[Bar <:< String]
                          ^
<console>:9: error: Cannot prove that Bar <:< String.
       val ev = implicitly[Bar <:< String]
                          ^

The compiler tries the Bar <:< Bar again, but since Bar isn't a String, this isn't a subtype of Bar <:< String, so it's not what we need. But $conforms is the only place the compiler can get <:< instances (unless we've defined our own, which would be dangerous), so it quite properly refuses to compile this nonsense.

To address your second question: the <:<[-From, +To] class is necessary because we need the type parameters for this type class to be useful. The singleton Any <:< Any value could just as well be defined as an object—the decision to use a val and an anonymous class is arguably a little simpler, but it's an implementation detail that you shouldn't ever need to worry about.

Great answer, thanks! Can you add some info on why it extends `(From => To)` and implements `apply`? I assume that method is never called. — Rag, Jun 02 '15 at 22:05
It does get used in many cases. Take the `toMap` definition, for example—[this line](https://github.com/scala/scala/blob/v2.11.6/src/library/scala/collection/TraversableOnce.scala#L302) wouldn't compile without an implicit conversion from `A` to `(T, U)` in scope. — Travis Brown, Jun 02 '15 at 22:14

How does the <:< operator work in Scala?

1 Answers1

Linked