Adding a `to[Col[_]]` method for a covariant collection

Question

I am implementing a data structure. While it doesn't directly mix in any of Scala's standard collection traits, I want to include the to[Col[_]] method which, given a builder factory, can generate standard Scala collections.

Now assume this, copied from GenTraversableOnce:

trait Foo[+A] {
  def to[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A]]): Col[A]
}

This fails with error: covariant type A occurs in invariant position.

So how can GenTraversableOnce achieve this? I can see in the source code, that they add an annotation.unchecked.uncheckedVariance...

That looks like a dirty trick. If the typer rejects this normally, how can this be safe and switched off with uncheckedVariance?

Answer 1

Variance checking is a very important part of type checking and skipping it may easily cause a runtime type error. Here I can demonstrate a type populated with an invalid runtime value by printing it. I've not been able to make it crash with an type cast exception yet though.

import collection.generic.CanBuildFrom
import collection.mutable.Builder
import scala.annotation.unchecked.uncheckedVariance

trait Foo[+A] {
  def toCol[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uncheckedVariance]]): Col[A @uncheckedVariance]
}

object NoStrings extends Foo[String] {
  override def toCol[Col[_]](implicit cbf: CanBuildFrom[Nothing, String, Col[String]]): Col[String] = {
    val res : Col[String] = cbf().result
    println("Printing a Col[String]: ")
    println(res)
    res
  }
}

case class ExactlyOne[T](t : T)

implicit def buildExactlyOne = new CanBuildFrom[Nothing, Any, ExactlyOne[Any]] {
  def apply() = new Builder[Any, ExactlyOne[Any]]  { 
    def result = ExactlyOne({}) 
    def clear = {}
    def +=(x : Any) = this
  }
  def apply(n : Nothing) = n
}

val noStrings : Foo[Any] = NoStrings
noStrings.toCol[ExactlyOne]

Here println(res) with res : Col[String] prints ExactlyOne(()). However, ExactlyOne(()) does not have a type of Col[String], demonstrating a type error.

To solve the problem while respecting variance rules we can move the invariant code out of the trait and only keep covariant part, while using implicit conversion to convert from covariant trait to invariant helper class:

import collection.generic.CanBuildFrom

trait Foo[+A] {
  def to[R](implicit cbf: CanBuildFrom[Nothing, A, R]): R
}

class EnrichedFoo[A](foo : Foo[A]) {
  def toCol[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A]]): Col[A] = 
    foo.to[Col[A]]
}

implicit def enrich[A](foo : Foo[A]) = new EnrichedFoo(foo)

case class Bar[A](elem: A) extends Foo[A] {
  def to[R](implicit cbf: CanBuildFrom[Nothing, A, R]): R = {
    val b = cbf()
    b += elem
    b.result()
  }
}

val bar1 = Bar(3)
println(bar1.toCol[Vector])