Scala 2.8 breakOut

225

W Scali 2.8 znajduje się obiekt w 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()
 }

Powiedziano mi, że skutkuje to:

> 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)

Co tu się dzieje? Dlaczego jest breakOutnazywany moim argumentemList ?

oxbow_lakes
źródło
13
Trywialna odpowiedź jest taka, że ​​nie jest to argument List, ale map.
Daniel C. Sobral

Odpowiedzi:

325

Odpowiedź znajduje się w definicji map:

def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That 

Zauważ, że ma dwa parametry. Pierwsza jest twoją funkcją, a druga jest niejawna. Jeśli nie podasz tego w sposób dorozumiany, Scala wybierze najbardziej konkretny z dostępnych.

O breakOut

Więc jaki jest cel breakOut? Rozważ przykład podany dla pytania: bierzesz listę ciągów, przekształcasz każdy ciąg w krotkę (Int, String), a następnie tworzysz Mapz niego. Najbardziej oczywistym sposobem na to byłoby utworzenie List[(Int, String)]kolekcji pośredniej , a następnie jej konwersja.

Biorąc pod uwagę, że mapużywa a Builderdo wytworzenia wynikowej kolekcji, czy nie byłoby możliwe pominięcie pośrednika Listi zebranie wyników bezpośrednio do Map? Oczywiście tak jest. Aby to zrobić, jednak musimy zdać właściwy CanBuildFromdo map, i to jest dokładnie to, co breakOutrobi.

Spójrzmy zatem na definicję 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()
  }

Zauważ, że breakOutjest sparametryzowane i zwraca instancję CanBuildFrom. Jak to się dzieje, rodzaje From, Ta Tojuż wywnioskować, ponieważ wiemy, że mapspodziewa CanBuildFrom[List[String], (Int, String), Map[Int, String]]. W związku z tym:

From = List[String]
T = (Int, String)
To = Map[Int, String]

Na zakończenie zbadajmy dorozumiane otrzymane przez breakOutsiebie. To jest rodzaj CanBuildFrom[Nothing,T,To]. Znamy już wszystkie te typy, więc możemy ustalić, że potrzebujemy niejawnego typu CanBuildFrom[Nothing,(Int,String),Map[Int,String]]. Ale czy istnieje taka definicja?

Spójrzmy na CanBuildFromdefinicję:

trait CanBuildFrom[-From, -Elem, +To] 
extends AnyRef

Podobnie CanBuildFromjest z wariantem pierwszego parametru typu. Ponieważ Nothingjest to najniższa klasa (tj. Podklasa wszystkiego), oznacza to, że można użyć dowolnej klasy zamiast Nothing.

Ponieważ taki konstruktor istnieje, Scala może go użyć do uzyskania pożądanego wyniku.

O konstruktorach

Wiele metod z biblioteki kolekcji Scali polega na pobraniu oryginalnej kolekcji, przetworzeniu jej w jakiś sposób (w przypadku mapprzekształcenia każdego elementu) i zapisaniu wyników w nowej kolekcji.

Aby zmaksymalizować ponowne użycie kodu, przechowywanie wyników odbywa się za pomocą narzędzia budującego ( scala.collection.mutable.Builder), które zasadniczo obsługuje dwie operacje: dodawanie elementów i zwracanie wynikowej kolekcji. Typ tej wynikowej kolekcji będzie zależeć od typu konstruktora. W ten sposób Listbudowniczy zwróci a List, Mapbudowniczy zwróci Mapa itd. Wdrożenie mapmetody nie musi dotyczyć rodzaju wyniku: zajmuje się nim konstruktor.

Z drugiej strony oznacza to, że mapmusi jakoś otrzymać tego konstruktora. Problemem podczas projektowania kolekcji Scala 2.8 było wybranie najlepszego konstruktora. Na przykład, gdybym miał pisać Map('a' -> 1).map(_.swap), chciałbym Map(1 -> 'a')odzyskać. Z drugiej strony, a Map('a' -> 1).map(_._1)nie może zwrócić a Map(zwraca an Iterable).

Magia tworzenia najlepszego możliwego Builderze znanych typów wyrażeń odbywa się za pośrednictwem tego CanBuildFromukrytego.

O CanBuildFrom

Aby lepiej wyjaśnić, co się dzieje, podam przykład, w którym odwzorowywana kolekcja jest Mapzamiast List. Wrócę do Listpóźniej. Na razie rozważmy te dwa wyrażenia:

Map(1 -> "one", 2 -> "two") map Function.tupled(_ -> _.length)
Map(1 -> "one", 2 -> "two") map (_._2)

Pierwszy zwraca a, Mapa drugi zwraca an Iterable. Magia zwrotu pasującej kolekcji jest dziełem CanBuildFrom. Rozważmy definicję mapponownie, aby ją zrozumieć.

Metoda mapjest dziedziczona z TraversableLike. Jest sparametryzowany na Bi Thatwykorzystuje parametry typu Ai Repr, które parametryzują klasę. Zobaczmy obie definicje razem:

Klasa TraversableLikejest zdefiniowana jako:

trait TraversableLike[+A, +Repr] 
extends HasNewBuilder[A, Repr] with AnyRef

def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That 

Aby zrozumieć, skąd Ai skąd Reprpochodzą, rozważmy definicję Mapsamego siebie:

trait Map[A, +B] 
extends Iterable[(A, B)] with Map[A, B] with MapLike[A, B, Map[A, B]]

Ponieważ TraversableLikejest dziedziczony przez wszystkie cechy, które się rozciągają Map, Ai Reprmoże zostać odziedziczony z dowolnej z nich. Ten ostatni ma jednak pierwszeństwo. Tak więc, zgodnie z definicją niezmiennego Mapi wszystkimi cechami, które go łączą TraversableLike, mamy:

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

Jeśli przekażesz parametry typu Map[Int, String]w dół łańcucha, okaże się, że typy przekazywane do TraversableLike, a zatem używane przez map, to:

A = (Int,String)
Repr = Map[Int, String]

Wracając do przykładu, pierwsza mapa odbiera funkcję typu, ((Int, String)) => (Int, Int)a druga mapa odbiera funkcję typu ((Int, String)) => String. Używam podwójnego nawiasu, aby podkreślić, że jest to krotka otrzymywana, jak to Awidzieliśmy.

Mając te informacje, rozważmy inne typy.

map Function.tupled(_ -> _.length):
B = (Int, Int)

map (_._2):
B = String

Widzimy, że typ zwracany przez pierwszy mapto Map[Int,Int], a drugi to Iterable[String]. Patrząc na mapdefinicję, łatwo zauważyć, że są to wartości That. Ale skąd one pochodzą?

Jeśli zajrzymy do obiektów towarzyszących zaangażowanych klas, zobaczymy, że zawierają je niejawne deklaracje. Na obiekt Map:

implicit def  canBuildFrom [A, B] : CanBuildFrom[Map, (A, B), Map[A, B]]  

I na obiekcie Iterable, którego klasa jest rozszerzona o Map:

implicit def  canBuildFrom [A] : CanBuildFrom[Iterable, A, Iterable[A]]  

Te definicje dostarczają fabryki sparametryzowane CanBuildFrom.

Scala wybierze najbardziej konkretny dostępny dorozumiany. W pierwszym przypadku był pierwszy CanBuildFrom. W drugim przypadku, ponieważ pierwszy nie pasował, wybrał drugi CanBuildFrom.

Powrót do pytania

Zobaczmy kod dla definicji pytania Listi mapdefinicji (ponownie), aby zobaczyć, w jaki sposób są wywnioskowane typy:

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 

Typ List("London", "Paris")jest List[String], więc typy Ai Reprzdefiniowane na TraversableLiketo:

A = String
Repr = List[String]

Typem (x => (x.length, x))jest (String) => (Int, String), więc typem Bjest:

B = (Int, String)

Ostatni nieznany typ Thatto typ wyniku map, który już mamy:

val map : Map[Int,String] =

Więc,

That = Map[Int, String]

Oznacza to breakOut, że musi koniecznie zwracać typ lub podtyp CanBuildFrom[List[String], (Int, String), Map[Int, String]].

Daniel C. Sobral
źródło
61
Daniel, mogę przeglądać typy w twojej odpowiedzi, ale kiedy doszedłem do końca, czuję, że nie zdobyłem żadnego zrozumienia na wysokim poziomie. Co to jest breakOut? Skąd pochodzi nazwa „breakOut” (z czego się wybijam)? Dlaczego jest to potrzebne w tym przypadku, aby uzyskać mapę? Czy jest jakiś sposób, aby krótko odpowiedzieć na te pytania? (nawet jeśli konieczne jest długotrwałe
marudzenie
3
@Seth To ważna kwestia, ale nie jestem pewien, czy wykonuję to zadanie. Pochodzenie tego można znaleźć tutaj: article.gmane.org/gmane.comp.lang.scala.internals/1812/... . Zastanowię się, ale w tej chwili nie mogę wymyślić żadnego sposobu, aby to poprawić.
Daniel C. Sobral
2
Czy istnieje sposób na uniknięcie określenia całego typu wyniku Map [Int, String] i zamiast tego możliwość napisania czegoś takiego: „val map = List („ London ”,„ Paris ”). Map (x => (x. length, x)) (breakOut [... Map]) '
IttayD
9
@SethTisue Z mojej lektury tego wyjaśnienia wydaje się, że breakOut jest konieczny, aby „zerwać” z wymogiem, który budowniczy musi zbudować z List [String]. Kompilator chce CanBuildFrom [List [Ciąg], (Int, Ciąg), Mapa [Int, Ciąg]], którego nie można dostarczyć. Funkcja breakOut robi to poprzez clobbering pierwszego parametru typu w CanBuildFrom poprzez ustawienie go na Nothing. Teraz musisz tylko podać CanBuildFrom [Nic, (Int, String), Map [Int, String]]. Jest to łatwe, ponieważ zapewnia klasa Map.
Mark
2
@Mark Kiedy znalazłem breakOut, problem, który widziałem, jak to rozwiązuje, to sposób, w jaki monady nalegają na mapowanie (przez bind / flatMap) na swój własny typ. Pozwala „wyrwać się” z łańcucha odwzorowania za pomocą jednej monady na inny typ monady. Nie mam jednak pojęcia, czy właśnie tak o tym myślał Adriaan Moors (autor)!
Ed Staub,
86

Chciałbym skorzystać z odpowiedzi Daniela. To było bardzo dokładne, ale jak zauważono w komentarzach, nie wyjaśnia, co robi breakout.

Zaczerpnięto z Re: Wsparcie dla jawnych konstruktorów (2009-10-23). ​​Oto, co moim zdaniem, Breakout:

Daje to kompilatorowi sugestię, który Konstruktor ma wybrać domyślnie (zasadniczo pozwala kompilatorowi wybrać, która fabryka, jego zdaniem, najlepiej pasuje do sytuacji).

Na przykład zobacz następujące:

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)

Możesz zobaczyć, że typ zwrotu jest domyślnie wybrany przez kompilator, aby jak najlepiej pasował do oczekiwanego typu. W zależności od tego, jak deklarujesz zmienną odbierającą, otrzymujesz różne wyniki.

Poniższy przykład byłby równoważnym sposobem określenia konstruktora. Uwaga: w tym przypadku kompilator wyliczy oczekiwany typ na podstawie typu konstruktora:

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)
Austen Holmes
źródło
1
Zastanawiam się, dlaczego nazywa się „ breakOut”? Myślę, że coś w stylu ( convertlub buildADifferentTypeOfCollectionkrótszego) mogłoby być łatwiejsze do zapamiętania.
KajMagnus
8

Odpowiedź Daniela Sobrala jest świetna i należy ją czytać razem z architekturą kolekcji Scala (rozdział 25 programowania w Scali).

Chciałem tylko wyjaśnić, dlaczego nazywa się to breakOut:

Dlaczego się nazywa breakOut?

Ponieważ chcemy wyrwać się z jednego typu na inny :

Wyłamać się z jakiego typu do jakiego typu? Spójrzmy na mapfunkcję Seqjako przykład:

Seq.map[B, That](f: (A) -> B)(implicit bf: CanBuildFrom[Seq[A], B, That]): That

Gdybyśmy chcieli zbudować mapę bezpośrednio z mapowania na elementach sekwencji, takich jak:

val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))

Kompilator narzekałby:

error: type mismatch;
found   : Seq[(String, Int)]
required: Map[String,Int]

Powodem jest to, że Seq wie tylko, jak zbudować kolejny Seq (tzn. Istnieje domyślna CanBuildFrom[Seq[_], B, Seq[B]]fabryka konstruktorów, ale NIE ma fabryki konstruktorów od Seq do Map).

Aby skompilować, musimy w jakiś sposób breakOutokreślić wymagania dotyczące typu i być w stanie zbudować konstruktor, który utworzy mapę mapdo użycia przez funkcję.

Jak wyjaśnił Daniel, breakOut ma następującą sygnaturę:

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()
    }

Nothingjest podklasą wszystkich klas, więc można zastąpić dowolną fabrykę konstruktorów implicit b: CanBuildFrom[Nothing, T, To]. Jeśli użyliśmy funkcji breakOut, aby podać niejawny parametr:

val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))(collection.breakOut)

Skompiluje się, ponieważ breakOutjest w stanie zapewnić wymagany typ CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]], podczas gdy kompilator jest w stanie znaleźć domyślną fabrykę konstruktora typu CanBuildFrom[Map[_, _], (A, B), Map[A, B]]zamiastCanBuildFrom[Nothing, T, To] , której breakOut może użyć do utworzenia rzeczywistego konstruktora.

Zauważ, że CanBuildFrom[Map[_, _], (A, B), Map[A, B]]jest zdefiniowane w Mapie i po prostu inicjuje mapę, MapBuilderktóra korzysta z podstawowej Mapy.

Mam nadzieję, że to wszystko wyjaśni.

Dzhu
źródło
4

Prosty przykład, aby zrozumieć, co 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]
fdietze
źródło
Dzięki za przykład! Również val seq:Seq[Int] = set.map(_ % 2).toVectornie daje powtarzające się wartości, jak Setzostała zachowana dla map.
Matthew Pickering,
@MatthewPickering poprawnie! set.map(_ % 2)tworzy Set(1, 0)pierwszy, który następnie jest konwertowany na Vector(1, 0).
fdietze