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?

score 2 · Answer 1 · edited May 23 '17 at 10:28

It can because it is using the @uncheckedVariance annotation to circumpass the type system and ignore variance checking.

Simply import scala.annotation.unchecked.uncheckedVariance and annotate the type for which you want the variance checking disabled:

def to[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uncheckedVariance]]): Col[A @uncheckedVariance]

See a more complete explanation in the related answer.

score 2 · Answer 2 · answered Mar 08 '13 at 18:56

I read the link to the other question mentioned by @axel22. It still doesn't appear to be the actual reason, though (allowing GenTraversableOnce to function both for variant and invariant collections—it is covariant in A).

For example, the following works correctly without coercing the typer:

import collection.generic.CanBuildFrom

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

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

This would in my opinion be the correct signature. But then of course, it gets ugly:

val b = Bar(33)
b.to[Int, Vector]

So, my interpretation of the use of @uncheckedVariance is merely to avoid having to repeat the element type (as upper bound) in the to signature.

That still doesn't answer, though, if we can imagine a case which results in a runtime error from neglecting the variance?

You don't really need `A` and `A1` related at all. This works too: `def to[B, Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[B]]): Col[B]`. Even this looks unnecessarily restrictive in that it only allows the result of the shape `Col[B]`. This looks more general and simple: `def to[R](implicit cbf: CanBuildFrom[Nothing, A, R]): R`. — Rotsor, Mar 08 '13 at 19:31

score 2 · Accepted Answer · answered Mar 08 '13 at 20:29

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])

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

3 Answers3