Example code for <http://stackoverflow.com/q/28947134/3625>.

AsyncMap.scala

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

class AsyncMapBuilder[A, B, Coll <: AsyncMap[A, B]](empty: Coll)
  extends Builder[(A, B), Coll]
{

  protected var elems: Coll = empty

  def +=(kv: (A, B)): this.type = {
    elems = (elems + kv).asInstanceOf[Coll]
    this
  }

  def clear() { elems = empty }

  def result: Coll = elems

}

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
  // have to block while it determines whether it contains an element for a
  // given key).
  def get(key: A): Future[Option[B]]

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

  /*
  // This blows up with an error message that seems totally unrelated to the actual problem:
  // "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]] = {
    new AsyncMapBuilder(empty)
  }
  */
  // This compiles!
  override protected[this] def newBuilder: Builder[(A, B), AsyncMap[A, B]] = {
    new AsyncMapBuilder(empty)
  }

}