创建`collection.mutable.SortedSet` - `map`方法中的歧义

Question

我正在尝试解决缺少的问题,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 )    
                                                      ^

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

Answer 1

看起来你需要canBuildFrom在object中定义一个方法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在Scala Collections的架构中编写了一个很好的文档,其中包括一个关于集成新集和地图的部分.虽然它非常难以找到,但如果您对构建自己的馆藏感兴趣,它是一个权威资源.