Scala 2.8 breakOut
В Scala 2.8 есть объект в scala.collection.package.scala:
def breakOut[From, T, To](implicit b : CanBuildFrom[Nothing, T, To]) =
new CanBuildFrom[From, T, To] {
def apply(from: From) = b.apply() ; def apply() = b.apply()
}
Мне сказали, что это приводит к:
> import scala.collection.breakOut
> val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x))(breakOut)
map: Map[Int,String] = Map(6 -> London, 5 -> Paris)
Что здесь происходит? Почему breakOut вызывается в качестве аргумента к моему List?
4 ответа
Ответ найден по определению map:
def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That
Обратите внимание, что у него есть два параметра. Первая - это ваша функция, а вторая - неявная. Если вы не укажете это неявно, Scala выберет наиболее конкретный из доступных.
ОколоbreakOut
Итак, какова цель breakOut? Рассмотрим пример, приведенный для вопроса. Вы берете список строк, превращаете каждую строку в кортеж. (Int, String), а затем произвести Map из этого. Самый очевидный способ сделать это - создать посредника. List[(Int, String)] Коллекция, а затем преобразовать его.
При условии map использует Builder чтобы создать итоговую коллекцию, нельзя было бы пропустить посредника List и собрать результаты непосредственно в Map? Очевидно, да, это так. Однако для этого нам необходимо пройти CanBuildFrom в mapи это именно то, что breakOut делает.
Давайте посмотрим на определение breakOut:
def breakOut[From, T, To](implicit b : CanBuildFrom[Nothing, T, To]) =
new CanBuildFrom[From, T, To] {
def apply(from: From) = b.apply() ; def apply() = b.apply()
}
Обратите внимание, что breakOut параметризован, и что он возвращает экземпляр CanBuildFrom, Как это бывает, типы From, T а также To уже был сделан вывод, потому что мы знаем, что map ожидает CanBuildFrom[List[String], (Int, String), Map[Int, String]], Следовательно:
From = List[String]
T = (Int, String)
To = Map[Int, String]
В заключение давайте рассмотрим неявное, полученное breakOut сам. Это типа CanBuildFrom[Nothing,T,To], Мы уже знаем все эти типы, поэтому мы можем определить, что нам нужен неявный тип CanBuildFrom[Nothing,(Int,String),Map[Int,String]], Но есть ли такое определение?
Давайте посмотрим на CanBuildFromопределение:
trait CanBuildFrom[-From, -Elem, +To]
extends AnyRef
Так CanBuildFrom является противоположным по параметру первого типа. Так как Nothing является нижним классом (т.е. это подкласс всего), это означает, что любой класс может быть использован вместо Nothing,
Поскольку такой компоновщик существует, Scala может использовать его для получения желаемого результата.
О строителях
Многие методы из библиотеки коллекций Scala состоят в том, чтобы взять оригинальную коллекцию, как-то ее обработать (в случае mapпреобразование каждого элемента) и сохранение результатов в новой коллекции.
Чтобы максимизировать повторное использование кода, это сохранение результатов осуществляется через конструктор (scala.collection.mutable.Builder), который в основном поддерживает две операции: добавление элементов и возврат полученной коллекции. Тип этой результирующей коллекции будет зависеть от типа компоновщика. Таким образом, List строитель вернет List, Map строитель вернет Map, и так далее. Реализация map Метод не должен заботиться о типе результата: об этом заботится строитель.
С другой стороны, это означает, что map Нужно как-то получить этого застройщика. При проектировании Scala 2.8 Collections была проблема выбора лучшего строителя. Например, если бы я должен был написать Map('a' -> 1).map(_.swap)Я хотел бы получить Map(1 -> 'a') назад. С другой стороны, Map('a' -> 1).map(_._1) не могу вернуть Map (возвращает Iterable).
Магия производства наилучшего Builder Из известных типов выражение выполняется через этот CanBuildFrom неявный.
ОколоCanBuildFrom
Чтобы лучше объяснить, что происходит, я приведу пример, где отображаемая коллекция является Map вместо List, Я вернусь к List потом. А пока рассмотрим эти два выражения:
Map(1 -> "one", 2 -> "two") map Function.tupled(_ -> _.length)
Map(1 -> "one", 2 -> "two") map (_._2)
Первый возвращает Map а второй возвращает Iterable, Волшебство возвращения подходящей коллекции - работа CanBuildFrom, Давайте рассмотрим определение map еще раз, чтобы понять это.
Метод map наследуется от TraversableLike, Параметризован на B а также Thatи использует параметры типа A а также Repr, которые параметризуют класс. Давайте посмотрим оба определения вместе:
Класс TraversableLike определяется как:
trait TraversableLike[+A, +Repr]
extends HasNewBuilder[A, Repr] with AnyRef
def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That
Чтобы понять где A а также Repr давай, давайте рассмотрим определение Map сам:
trait Map[A, +B]
extends Iterable[(A, B)] with Map[A, B] with MapLike[A, B, Map[A, B]]
Так как TraversableLike наследуется всеми признаками, которые распространяются Map, A а также Repr может быть унаследован от любого из них. Последний получает предпочтение, хотя. Итак, следуя определению неизменного Map и все черты, которые связывают его с TraversableLike, у нас есть:
trait Map[A, +B]
extends Iterable[(A, B)] with Map[A, B] with MapLike[A, B, Map[A, B]]
trait MapLike[A, +B, +This <: MapLike[A, B, This] with Map[A, B]]
extends MapLike[A, B, This]
trait MapLike[A, +B, +This <: MapLike[A, B, This] with Map[A, B]]
extends PartialFunction[A, B] with IterableLike[(A, B), This] with Subtractable[A, This]
trait IterableLike[+A, +Repr]
extends Equals with TraversableLike[A, Repr]
trait TraversableLike[+A, +Repr]
extends HasNewBuilder[A, Repr] with AnyRef
Если вы передаете параметры типа Map[Int, String] на всем пути вниз мы обнаруживаем, что типы, переданные TraversableLikeи, таким образом, используется map, являются:
A = (Int,String)
Repr = Map[Int, String]
Возвращаясь к примеру, первая карта получает функцию типа ((Int, String)) => (Int, Int) а вторая карта получает функцию типа ((Int, String)) => String, Я использую двойные скобки, чтобы подчеркнуть, что получен кортеж, так как это тип A как мы видели.
С этой информацией, давайте рассмотрим другие типы.
map Function.tupled(_ -> _.length):
B = (Int, Int)
map (_._2):
B = String
Мы можем видеть, что тип, возвращаемый первым map является Map[Int,Int]и второе Iterable[String], Смотря на mapпо определению легко увидеть, что это значения That, Но откуда они берутся?
Если мы посмотрим внутрь сопутствующих объектов участвующих классов, мы увидим некоторые неявные объявления, предоставляющие их. На объекте Map:
implicit def canBuildFrom [A, B] : CanBuildFrom[Map, (A, B), Map[A, B]]
И на объекте Iterableчей класс расширен на Map:
implicit def canBuildFrom [A] : CanBuildFrom[Iterable, A, Iterable[A]]
Эти определения обеспечивают фабрики для параметризованных CanBuildFrom,
Scala выберет наиболее конкретную неявную версию из доступных. В первом случае это был первый CanBuildFrom, Во втором случае, так как первый не совпал, он выбрал второй CanBuildFrom,
Вернуться к вопросу
Давайте посмотрим код для вопроса, Listи mapопределение (снова), чтобы увидеть, как типы выводятся:
val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x))(breakOut)
sealed abstract class List[+A]
extends LinearSeq[A] with Product with GenericTraversableTemplate[A, List] with LinearSeqLike[A, List[A]]
trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]]
extends SeqLike[A, Repr]
trait SeqLike[+A, +Repr]
extends IterableLike[A, Repr]
trait IterableLike[+A, +Repr]
extends Equals with TraversableLike[A, Repr]
trait TraversableLike[+A, +Repr]
extends HasNewBuilder[A, Repr] with AnyRef
def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That
Тип List("London", "Paris") является List[String]Итак, типы A а также Repr определено на TraversableLike являются:
A = String
Repr = List[String]
Тип для (x => (x.length, x)) является (String) => (Int, String)так что тип B является:
B = (Int, String)
Последний неизвестный тип, That тип результата mapи это у нас уже есть:
val map : Map[Int,String] =
Так,
That = Map[Int, String]
Это означает breakOut должен обязательно возвращать тип или подтип CanBuildFrom[List[String], (Int, String), Map[Int, String]],
Я хотел бы опираться на ответ Дэниела. Это было очень тщательно, но, как отмечено в комментариях, это не объясняет, что делает прорыв.
Взятый из Re: Поддержка явных Строителей (2009-10-23), вот что я считаю прорывом:
Он дает компилятору предложение о том, какой Builder выбирать неявно (по сути, он позволяет компилятору выбирать, какую фабрику он считает наиболее подходящей для ситуации).
Например, смотрите следующее:
scala> import scala.collection.generic._
import scala.collection.generic._
scala> import scala.collection._
import scala.collection._
scala> import scala.collection.mutable._
import scala.collection.mutable._
scala>
scala> def breakOut[From, T, To](implicit b : CanBuildFrom[Nothing, T, To]) =
| new CanBuildFrom[From, T, To] {
| def apply(from: From) = b.apply() ; def apply() = b.apply()
| }
breakOut: [From, T, To]
| (implicit b: scala.collection.generic.CanBuildFrom[Nothing,T,To])
| java.lang.Object with
| scala.collection.generic.CanBuildFrom[From,T,To]
scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)
scala> val imp = l.map(_ + 1)(breakOut)
imp: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 3, 4)
scala> val arr: Array[Int] = l.map(_ + 1)(breakOut)
imp: Array[Int] = Array(2, 3, 4)
scala> val stream: Stream[Int] = l.map(_ + 1)(breakOut)
stream: Stream[Int] = Stream(2, ?)
scala> val seq: Seq[Int] = l.map(_ + 1)(breakOut)
seq: scala.collection.mutable.Seq[Int] = ArrayBuffer(2, 3, 4)
scala> val set: Set[Int] = l.map(_ + 1)(breakOut)
seq: scala.collection.mutable.Set[Int] = Set(2, 4, 3)
scala> val hashSet: HashSet[Int] = l.map(_ + 1)(breakOut)
seq: scala.collection.mutable.HashSet[Int] = Set(2, 4, 3)
Вы можете видеть, что возвращаемый тип неявно выбирается компилятором, чтобы наилучшим образом соответствовать ожидаемому типу. В зависимости от того, как вы объявите получающую переменную, вы получите разные результаты.
Следующее будет эквивалентным способом указать конструктор. Обратите внимание, что в этом случае компилятор выведет ожидаемый тип в зависимости от типа компоновщика:
scala> def buildWith[From, T, To](b : Builder[T, To]) =
| new CanBuildFrom[From, T, To] {
| def apply(from: From) = b ; def apply() = b
| }
buildWith: [From, T, To]
| (b: scala.collection.mutable.Builder[T,To])
| java.lang.Object with
| scala.collection.generic.CanBuildFrom[From,T,To]
scala> val a = l.map(_ + 1)(buildWith(Array.newBuilder[Int]))
a: Array[Int] = Array(2, 3, 4)
Ответ Даниэля Собрала велик, и его следует читать вместе с " Архитектурой коллекций Scala" (глава 25 "Программирование в Scala").
Я просто хотел уточнить, почему это называется breakOut:
Почему это называется breakOut?
Потому что мы хотим вырваться из одного типа в другой:
Вырваться из какого типа в какой тип? Давайте посмотрим на map функция на Seq В качестве примера:
Seq.map[B, That](f: (A) -> B)(implicit bf: CanBuildFrom[Seq[A], B, That]): That
Если мы хотим построить карту непосредственно из отображения элементов последовательности, таких как:
val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))
Компилятор будет жаловаться:
error: type mismatch;
found : Seq[(String, Int)]
required: Map[String,Int]
Причина в том, что Seq знает только, как построить другой Seq (т.е. существует неявный CanBuildFrom[Seq[_], B, Seq[B]] Строительная фабрика доступна, но НЕТ строительной фабрики от Сека до Карты).
Для того, чтобы скомпилировать, нам нужно как-то breakOutтребования типа и быть в состоянии построить конструктор, который создает карту для map функция для использования.
Как объяснил Даниэль, breakOut имеет следующую подпись:
def breakOut[From, T, To](implicit b: CanBuildFrom[Nothing, T, To]): CanBuildFrom[From, T, To] =
// can't just return b because the argument to apply could be cast to From in b
new CanBuildFrom[From, T, To] {
def apply(from: From) = b.apply()
def apply() = b.apply()
}
Nothing является подклассом всех классов, поэтому любая фабрика компоновщика может быть заменена вместо implicit b: CanBuildFrom[Nothing, T, To], Если мы использовали функцию breakOut для предоставления неявного параметра:
val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))(collection.breakOut)
Было бы скомпилировать, потому что breakOut способен обеспечить требуемый тип CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]]в то время как компилятор может найти фабрику неявного компоновщика типа CanBuildFrom[Map[_, _], (A, B), Map[A, B]], на месте CanBuildFrom[Nothing, T, To], для breakOut использовать для создания фактического строителя.
Обратите внимание, что CanBuildFrom[Map[_, _], (A, B), Map[A, B]] определяется в карте, и просто инициирует MapBuilder который использует базовую карту.
Надеюсь, это прояснит ситуацию.
Простой пример, чтобы понять, что breakOut делает:
scala> import collection.breakOut
import collection.breakOut
scala> val set = Set(1, 2, 3, 4)
set: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)
scala> set.map(_ % 2)
res0: scala.collection.immutable.Set[Int] = Set(1, 0)
scala> val seq:Seq[Int] = set.map(_ % 2)(breakOut)
seq: Seq[Int] = Vector(1, 0, 1, 0) // map created a Seq[Int] instead of the default Set[Int]