scala - 创建一个`collection.mutable.SortedSet` —`map`方法中的歧义

我正在尝试解决缺少collection.mutable.SortedSet的问题，这就是我的跳过列表实现。我快到了:

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")
}

好的，这可以编译。但与不变的排序集不同，我可以明确地做到这一点

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

这对于我可变的排序集失败了:

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

与

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

这超出了我的概述。关于如何实现不可变排序集已有的任何线索？我有机会消除这种歧义吗？

最佳答案

看来您需要在对象canBuildFrom中定义SkipList方法。虽然不需要这样做，但是定义自己的canBuildFrom的目的是确保继承的方法返回最佳类型。由于您混入了两个特征，因此如果您未定义自己的隐式canBuildFrom，则会造成歧义。

就您而言，添加类似的内容，

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

应该可以。

几个月前，Martin撰写了一份不错的文档，内容涉及在The Architecture of Scala Collections中实现自定义集合，其中包括section on integrating new sets and maps。虽然很难找到它，但是如果您有兴趣构建自己的收藏集，那么这是一个权威的资源。