Создание `collection.mutable.SortedSet` - неоднозначность в методе` map` - PullRequest
Новая
       44

Создание `collection.mutable.SortedSet` - неоднозначность в методе` map`

3 голосов
/ 20 июля 2011

Я пытаюсь обойти отсутствие 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 )    
                                                      ^

Этоза пределами моего обзора.Любые подсказки о том, как добиться того, что уже делает неизменный отсортированный набор?Есть ли шанс, что я смогу устранить эту двусмысленность?

Ответы [ 2 ]

7 голосов
/ 20 июля 2011

Похоже, вам нужно определить 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]
}

должно помочь.

Несколько месяцев назад Мартин написал хороший документ о реализации пользовательских коллекций в Архитектура коллекций Scala , которая включает в себя раздел по интеграции новых наборов и карт .Хотя его очень сложно найти, он является решающим ресурсом, если вы заинтересованы в создании своих собственных коллекций.

2 голосов
/ 20 июля 2011

При правильном implicit def canBuildFrom это возможно. Я удалил все миксины из SortedSet сейчас, потому что моя фактическая реализация принимает не только Ordering, но и другой параметр доказательства. Поэтому я заново добавил несколько бит из SortedSet. Решение: 

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

Тест компилирует (и работает в фактической реализации, которая здесь для краткости опущена): 

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