Должно ли Scala map () вести себя по-разному при отображении на тот же тип? - PullRequest
Новая
       13

Должно ли Scala map () вести себя по-разному при отображении на тот же тип?

5 голосов
/ 15 апреля 2011

В фреймворке Scala Collections я думаю, что при использовании map().

существуют некоторые поведения, которые противоречат друг другу. Мы можем различать два вида преобразований в (неизменяемых) коллекциях.Те, чья реализация вызывает newBuilder для воссоздания результирующей коллекции, и те, кто идет неявным CanBuildFrom, чтобы получить конструктор.

Первая категория содержит все преобразования, в которых тип содержащихся элементов не изменяется,Это, например, filter, partition, drop, take, span и т. Д. Эти преобразования могут вызывать newBuilder и воссоздавать тот же тип коллекции, что и тот, который они называютнезависимо от того, насколько конкретно: фильтрация List[Int] всегда может вернуть List[Int];фильтрация BitSet (или пример структуры RNA, описанной в этой статье об архитектуре инфраструктуры коллекций ) всегда может вернуть другое BitSet (или RNA).Давайте назовем их фильтрующими преобразованиями .

Второй категории преобразований требуется CanBuildFrom s, чтобы быть более гибкими, поскольку тип содержащихся элементов может измениться, и в результате этоготип самой коллекции, возможно, не может быть повторно использован: a BitSet не может содержать String s;RNA содержит только Base с.Примерами таких преобразований являются map, flatMap, collect, scanLeft, ++ и т. Д. Давайте назовем их преобразованиями отображения .

Теперь вот основныевопрос для обсуждения.Независимо от того, какой статический тип коллекции, все преобразования фильтрации будут возвращать один и тот же тип коллекции, в то время как тип коллекции, возвращаемый операцией отображения, может варьироваться в зависимости от статического типа. 

scala> import collection.immutable.TreeSet
import collection.immutable.TreeSet

scala> val treeset = TreeSet(1,2,3,4,5) // static type == dynamic type
treeset: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 2, 3, 4, 5)

scala> val set: Set[Int] = TreeSet(1,2,3,4,5) // static type != dynamic type
set: Set[Int] = TreeSet(1, 2, 3, 4, 5)

scala> treeset.filter(_ % 2 == 0)
res0: scala.collection.immutable.TreeSet[Int] = TreeSet(2, 4) // fine, a TreeSet again

scala> set.filter(_ % 2 == 0)    
res1: scala.collection.immutable.Set[Int] = TreeSet(2, 4) // fine

scala> treeset.map(_ + 1)        
res2: scala.collection.immutable.SortedSet[Int] = TreeSet(2, 3, 4, 5, 6) // still fine

scala> set.map(_ + 1)    
res3: scala.collection.immutable.Set[Int] = Set(4, 5, 6, 2, 3) // uh?!

Теперь японять, почему это работает такОбъясняется там и там .Вкратце: неявный CanBuildFrom вставляется на основе статического типа, и, в зависимости от реализации его метода def apply(from: Coll), может или не сможет воссоздать тот же тип коллекции.

Теперь мойЕдинственное, что, когда мы знаем, что мы используем операцию отображения, дающую коллекцию с элементом того же типа (который статически может определять компилятор), мы можем имитировать работу фильтрующих преобразований и использовать коллекциюродной строитель.Мы можем повторно использовать BitSet при отображении на Int с, создать новый TreeSet с тем же порядком и т. Д.

Тогда мы бы избежали случаев, когда 

for (i <- set) {
  val x = i + 1
  println(x)
}

невыведите увеличенные элементы TreeSet в том же порядке, что и 

for (i <- set; x = i + 1)
  println(x)

Итак:

  • Считаете ли вы, что было бы хорошей идеей изменить поведение отображенияпреобразований, как описано?
  • Какие неизбежные предостережения я сильно упустил из виду?
  • Как это можно осуществить?

Я думал о чем-то вроде implicit sameTypeEvidence: A =:= B параметр, возможно со значением по умолчанию null (или, скорее, implicit canReuseCalleeBuilderEvidence: B <:< A = null), который может быть использован во время выполнения, чтобы дать больше информации для CanBuildFrom, который, в свою очередь, может быть использован для определения типа компоновщика длявернуться.

1 Ответ

1 голос
/ 17 апреля 2011

Я снова посмотрел на нее, и я думаю, что ваша проблема не в конкретном недостатке коллекций Scala, а в отсутствии компоновщика TreeSet. Потому что следующее работает как задумано: 

val list = List(1,2,3,4,5)
val seq1: Seq[Int] = list
seq1.map( _ + 1 ) // yields List

val vector = Vector(1,2,3,4,5)
val seq2: Seq[Int] = vector
seq2.map( _ + 1 ) // yields Vector

Итак, причина в том, что TreeSet отсутствует специализированный сопутствующий объект / строитель: 

seq1.companion.newBuilder[Int]    // ListBuffer
seq2.companion.newBuilder[Int]    // VectorBuilder
treeset.companion.newBuilder[Int] // Set (oops!)

Так что я предполагаю, что если вы примете надлежащие меры для такого компаньона для вашего RNA класса, вы можете обнаружить, что и map, и filter работают, как вы хотите ...?

...