scala - 创建 `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

看起来您需要在对象 SkipList 中定义一个 canBuildFrom 方法。虽然这样做不是必需的，但定义您自己的 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 .虽然很难找到，但如果您有兴趣建立自己的收藏，它是一种权威资源。