How to implement newBuilder for a custom Scala collection (with correct variance)?

Question

I'm attempting to implement a new collection type which follows the same idioms as the standard library, but am having trouble figuring out how to handle the Builder mechanics. I've read through the excellent "Architecture of Scala Collections" doc page, but it doesn't cover my situation.

Here's a simplified version of what I'm trying to do:

import scala.collection.TraversableLike
import scala.concurrent.Future

trait AsyncMap[A, +B]
  extends Traversable[(A, B)]
  with TraversableLike[(A, B), AsyncMap[A, B]]
{

  def empty: AsyncMap[A, B]

  // This is the main difference from scala.collection.Map (an AsyncMap doesn't
  // block while it checks if it contains an element for a given key).
  def get(key: A): Future[Option[B]]

  def +[B1 >: B](kv: (A, B1)): AsyncMap[A, B1]

}

Compiling the above code gives me an error:

error: overriding method newBuilder in trait TraversableLike of type => scala.collection.mutable.Builder[(A, B),AsyncMap[A,B]];
 method newBuilder in trait GenericTraversableTemplate of type => scala.collection.mutable.Builder[(A, B),Traversable[(A, B)]] has incompatible type
trait AsyncMap[A, +B]
      ^

I think what this is complaining about is that GenericTraversableTemplate has a concrete newBuilder implementation whose signature is incompatible with the one that TraversableLike is looking for. What I don't understand is how I can get around this.

Implementing newBuilder: Builder[(A, B), Traversable[(A, B)]] produces this error:

error: overriding method newBuilder in trait TraversableLike of type => scala.collection.mutable.Builder[(A, B),AsyncMap[A,B]];
 method newBuilder has incompatible type
  override def newBuilder: Builder[(A, B), Traversable[(A, B)]] = {
               ^

While implementing newBuilder: Builder[(A, B), AsyncMap[A, B]] produces this error:

error: covariant type B occurs in contravariant position in type => scala.collection.mutable.Builder[(A, B),AsyncMap[A,B]] of method newBuilder
  override def newBuilder: Builder[(A, B), AsyncMap[A, B]] = {
               ^

I think I'm on the right track with the latter approach, but am not sure how to specify the variance here.

I've also tried making this look more like the internal collections by implementing a trait AsyncMapLike[A, +B, +This <: AsyncMapLike[A, B, This] with AsyncMap[A, B]], but that approach hasn't borne any fruit.

I should admit that I'm pretty new to Scala and while I think I understand its type system I could be unaware of some type operator or simple design pattern that solves this.

Any help would be greatly appreciated.

Possibly-related questions:

Would it be possible to use a more specialized partial implementation for your custom map trait, e.g. `MapLike` - No, _"The trouble with this approach is that I want `.get` to return a `Future[Option[B]]`, not a `Option[Future[B]]`. The intention is to allow AsyncMap implementations to be backed by slow external data sources (DB, web service, etc)"_ — mucaho, Mar 09 '15 at 21:12
Could you show your current implementation of `override protected[this] def newBuilder: Builder[(A, B), AsyncMap[A, B]]`? When left unimplemented, produces no compile errors. — mucaho, Mar 09 '15 at 21:14
@mucaho Maybe I was misusing access modifiers? I had previously overridden `newBuilder` with a public def, but when I use `protected[this]` it does indeed compile (for example, [this code](https://gist.github.com/mkantor/33acf84f16591f417d6e) works). What's going on here? Scala is supposed to allow increasing access scope from subclasses/traits, and the error message I got when it was public makes absolutely no sense. Why would the compiler complain about `B`'s variance? — Matt Kantor, Mar 10 '15 at 16:56
If that solves your problem I suggest you answer your own question and mark it as accepted and then ask a new question about why widening access modifiers gives you this error. (I can't even make an educated guess about what's going on here. Mysterious are the ways of scala :) ) — mucaho, Mar 10 '15 at 17:38

score 1 · Accepted Answer · edited May 23 '17 at 12:33

As mucaho helped me discover in the comments above, it turns out that my problem was caused by a missing access modifier. The error message about variance still doesn't make sense to me (I've opened a new question about it: Why does scalac only emit variance errors with certain access modifiers?), but when I override newBuilder with a concrete implementation whose access is protected[this], everything works as expected (previously I had been trying to make it public).

import scala.collection.mutable.Builder
import scala.collection.TraversableLike
import scala.concurrent.Future

trait AsyncMap[A, +B]
  extends Traversable[(A, B)]
  with TraversableLike[(A, B), AsyncMap[A, B]]
{
  def empty: AsyncMap[A, B]

  def get(key: A): Future[Option[B]]

  def +[B1 >: B](kv: (A, B1)): AsyncMap[A, B1]

  // This works!
  override protected[this] def newBuilder: Builder[(A, B), AsyncMap[A, B]] = ???
}

How to implement newBuilder for a custom Scala collection (with correct variance)?

1 Answers1

Linked