Creating a `collection.mutable.SortedSet` -- ambiguity in `map` method

Question

I am trying to work around the lack of a collection.mutable.SortedSet which is what my skip list implementation would be. I am almost there:

import collection.{SortedSet => CSortedSet, SortedSetLike => CSortedSetLike}
import collection.mutable.{Set => MSet, SetLike => MSetLike}
import collection.generic.{MutableSetFactory, GenericCompanion}

object SkipList extends MutableSetFactory[SkipList] {
  def empty[A](implicit ord: Ordering[A]): SkipList[A] = ???
}

trait SkipList[A] extends MSet[A] with MSetLike[A, SkipList[A]] with CSortedSet[A]
  with CSortedSetLike[A, SkipList[A]] {

  override def empty: SkipList[A] = SkipList.empty[A](ordering)

  def rangeImpl(from: Option[A], until: Option[A]): SkipList[A] =
    throw new Exception("Unsupported operation")
}

Ok, this compiles. But unlike the immutable sorted set, where I can unambiguously do

case class Holder(i: Int) extends Ordered[Holder] {
  def compare(b: Holder) = i.compare(b.i)
}

def test1(iss: ISortedSet[Holder]) = iss.map(_.i)

test1(ISortedSet(Holder(4), Holder(77), Holder(-2))).toList

this fails for my mutable sorted set:

def test2(sl: SkipList[Holder]) = sl.map(_.i)

with

error: ambiguous implicit values:
 both method canBuildFrom in object SortedSet of type [A](implicit ord: Ordering[A])scala.collection.generic.CanBuildFrom[scala.collection.SortedSet.Coll,A,scala.collection.SortedSet[A]]
 and method canBuildFrom in object Set of type [A]=> scala.collection.generic.CanBuildFrom[scala.collection.mutable.Set.Coll,A,scala.collection.mutable.Set[A]]
 match expected type scala.collection.generic.CanBuildFrom[SkipList[Holder],Int,That]
           def test2( sl: SkipList[ Holder ]) = sl.map( _.i )    
                                                      ^

This is beyond my overview. Any clues as how to achieve what the immutable sorted set already does? Any chance I can remove this ambiguity?

Answer 1

It looks like you need to define a canBuildFrom method in object SkipList. While doing so is not required, the purpose of defining your own canBuildFrom is to ensure that inherited methods return the best possible type. Since you're mixing in a couple of traits, it's creates an ambiguity if you're not defining your own implicit canBuildFrom.

In your case, adding something like,

import collection.generic.{CanBuildFrom, MutableSetFactory}
import collection.mutable.{Set, SetLike}

object SkipList extends MutableSetFactory[SkipList] {

  implicit def canBuildFrom[A : Ordering]: CanBuildFrom[Coll, A, SkipList[A]] =
    new CanBuildFrom[Coll, A, SkipList[A]] {
      def apply(from: Coll) = newBuilder[A]
      def apply() = newBuilder[A]
    }
}

trait SkipList[A]
extends Set[A] with SetLike[A, SkipList[A]] {
   override def empty: SkipList[A] = SkipList.empty[A]
}

should do the trick.

Martin wrote up a nice document a few months ago on implementing custom collections in The Architecture of Scala Collections, which includes a section on integrating new sets and maps. While it's terribly difficult to find, it's a definitive resource if you're interested in building your own collections.

Answer 2

With the proper implicit def canBuildFrom it is possible. I removed any mixins from SortedSet now, because my actual implementation not only takes an Ordering but also another evidence parameter. So I re-added a few bits from SortedSet. The solution is:

import collection.generic.CanBuildFrom
import collection.mutable.{Builder, Set => MSet, SetBuilder => MSetBuilder,
  SetLike => MSetLike}

object SkipList {
  def empty[A](implicit ord: Ordering[A]): SkipList[A] = ???

  private type CC[A] = SkipList[A]
  private type Coll = CC[_]

  implicit def canBuildFrom[A: Ordering]: CanBuildFrom[Coll, A, CC[A]] =
    new SkipListCanBuildFrom

  private class SkipListCanBuildFrom[A: Ordering]
    extends CanBuildFrom[Coll, A, CC[A]] {

    def apply(from: Coll) = newBuilder[A]
    def apply() = newBuilder[A]
  }

  def newBuilder[A: Ordering]: Builder[A, CC[A]] = new MSetBuilder(empty[A])
}

trait SkipList[A] extends MSet[A] with MSetLike[A, SkipList[A]] {
  override def empty: SkipList[A] = SkipList.empty[A](ordering)
  implicit def ordering: Ordering[A]
}

Test compiles (and works in the actual implementation which is omitted here for brevity):

case class Holder(i: Int)
def test2(sl: SkipList[Holder]): SkipList[Int] = sl.map(_.i + 1)