Scala 2.8 突破

Scala 2.8 breakOut

提问by oxbow_lakes

In Scala 2.8, there is an object in scala.collection.package.scala:

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

I have been told that this results in:

有人告诉我，这会导致：

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

What is going on here? Why is breakOutbeing called as an argumentto my List?

这里发生了什么？为什么breakOut被称为my的参数List？

回答by Daniel C. Sobral

The answer is found on the definition of map:

答案可在 的定义中找到map：

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

Note that it has two parameters. The first is your function and the second is an implicit. If you do not provide that implicit, Scala will choose the most specificone available.

请注意，它有两个参数。第一个是你的函数，第二个是隐式的。如果您不提供隐式，Scala 将选择可用的最具体的一个。

About breakOut

关于 breakOut

So, what's the purpose of breakOut? Consider the example given for the question, You take a list of strings, transform each string into a tuple (Int, String), and then produce a Mapout of it. The most obvious way to do that would produce an intermediary List[(Int, String)]collection, and then convert it.

那么，这样做的目的是breakOut什么？考虑为问题给出的示例，您获取一个字符串列表，将每个字符串转换为一个元组(Int, String)，然后从中生成一个Map。最明显的方法是生成一个中间List[(Int, String)]集合，然后转换它。

Given that mapuses a Builderto produce the resulting collection, wouldn't it be possible to skip the intermediary Listand collect the results directly into a Map? Evidently, yes, it is. To do so, however, we need to pass a proper CanBuildFromto map, and that is exactly what breakOutdoes.

鉴于map使用 aBuilder生成结果集合，是否可以跳过中介List并将结果直接收集到 a 中Map？显然，是的，确实如此。然而，要做到这一点，我们需要将一个专有参数传递CanBuildFrom给map，而这正是breakOut它所做的。

Let's look, then, at the definition of 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()
  }

Note that breakOutis parameterized, and that it returns an instance of CanBuildFrom. As it happens, the types From, Tand Tohave already been inferred, because we know that mapis expecting CanBuildFrom[List[String], (Int, String), Map[Int, String]]. Therefore:

请注意breakOut是参数化的，并且它返回 的实例CanBuildFrom。碰巧，类型From,T和To已经被推断出来，因为我们知道这map是期待CanBuildFrom[List[String], (Int, String), Map[Int, String]]。所以：

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

To conclude let's examine the implicit received by breakOutitself. It is of type CanBuildFrom[Nothing,T,To]. We already know all these types, so we can determine that we need an implicit of type CanBuildFrom[Nothing,(Int,String),Map[Int,String]]. But is there such a definition?

最后，让我们检查breakOut自身接收到的隐式。它的类型是CanBuildFrom[Nothing,T,To]。我们已经知道所有这些类型，所以我们可以确定我们需要一个隐式的 type CanBuildFrom[Nothing,(Int,String),Map[Int,String]]。但是有这样的定义吗？

Let's look at CanBuildFrom's definition:

让我们看看CanBuildFrom的定义：

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

So CanBuildFromis contra-variant on its first type parameter. Because Nothingis a bottom class (ie, it is a subclass of everything), that means anyclass can be used in place of Nothing.

所以CanBuildFrom它的第一个类型参数是逆变的。因为Nothing是底层类（即，它是所有东西的子类），这意味着可以使用任何类来代替Nothing.

Since such a builder exists, Scala can use it to produce the desired output.

由于存在这样的构建器，Scala 可以使用它来生成所需的输出。

About Builders

关于建造者

A lot of methods from Scala's collections library consists of taking the original collection, processing it somehow (in the case of map, transforming each element), and storing the results in a new collection.

Scala 集合库中的许多方法包括获取原始集合，以某种方式处理它（在 的情况下map，转换每个元素），并将结果存储在新集合中。

To maximize code reuse, this storing of results is done through a builder(scala.collection.mutable.Builder), which basically supports two operations: appending elements, and returning the resulting collection. The type of this resulting collection will depend on the type of the builder. Thus, a Listbuilder will return a List, a Mapbuilder will return a Map, and so on. The implementation of the mapmethod need not concern itself with the type of the result: the builder takes care of it.

为了最大限度地重用代码，这种结果的存储是通过构建器( scala.collection.mutable.Builder) 完成的，它基本上支持两种操作：附加元素和返回结果集合。此结果集合的类型将取决于构建器的类型。因此，List构建器将返回 a List，Map构建器将返回 a Map，依此类推。map方法的实现不需要关心结果的类型：构建器会处理它。

On the other hand, that means that mapneeds to receive this builder somehow. The problem faced when designing Scala 2.8 Collections was how to choose the best builder possible. For example, if I were to write Map('a' -> 1).map(_.swap), I'd like to get a Map(1 -> 'a')back. On the other hand, a Map('a' -> 1).map(_._1)can't return a Map(it returns an Iterable).

另一方面，这意味着map需要以某种方式接收这个构建器。设计 Scala 2.8 Collections 时面临的问题是如何选择最好的构建器。例如，如果我要写Map('a' -> 1).map(_.swap)，我想得到Map(1 -> 'a')回报。另一方面， aMap('a' -> 1).map(_._1)不能返回 a Map（它返回 an Iterable）。

The magic of producing the best possible Builderfrom the known types of the expression is performed through this CanBuildFromimplicit.

Builder从表达式的已知类型中产生最好的魔法是通过这个CanBuildFrom隐式执行的。

About CanBuildFrom

关于 CanBuildFrom

To better explain what's going on, I'll give an example where the collection being mapped is a Mapinstead of a List. I'll go back to Listlater. For now, consider these two expressions:

为了更好地解释发生了什么，我将举一个例子，其中被映射的集合是 aMap而不是List。List稍后我会回去。现在，考虑这两个表达式：

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

The first returns a Mapand the second returns an Iterable. The magic of returning a fitting collection is the work of CanBuildFrom. Let's consider the definition of mapagain to understand it.

第一个返回 a Map，第二个返回 a Iterable。返回合适集合的神奇之处在于CanBuildFrom. 让我们map再考虑一下 的定义来理解它。

The method mapis inherited from TraversableLike. It is parameterized on Band That, and makes use of the type parameters Aand Repr, which parameterize the class. Let's see both definitions together:

该方法map继承自TraversableLike. 它在Band上参数化That，并使用类型参数Aand Repr，后者参数化类。让我们一起看看这两个定义：

The class TraversableLikeis defined as:

该类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 

To understand where Aand Reprcome from, let's consider the definition of Mapitself:

要明白的地方A和Repr来自何方，让我们考虑的定义Map本身：

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

Because TraversableLikeis inherited by all traits which extend Map, Aand Reprcould be inherited from any of them. The last one gets the preference, though. So, following the definition of the immutable Mapand all the traits that connect it to TraversableLike, we have:

因为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

If you pass the type parameters of Map[Int, String]all the way down the chain, we find that the types passed to TraversableLike, and, thus, used by map, are:

如果Map[Int, String]沿链向下传递类型参数，我们会发现传递给 的类型TraversableLike，因此，被 使用的类型map是：

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

Going back to the example, the first map is receiving a function of type ((Int, String)) => (Int, Int)and the second map is receiving a function of type ((Int, String)) => String. I use the double parenthesis to emphasize it is a tuple being received, as that's the type of Aas we saw.

回到这个例子，第一个 map 接收一个 type 的函数，((Int, String)) => (Int, Int)第二个 map 接收一个 type 的函数((Int, String)) => String。我使用双括号来强调它是一个正在接收的元组，因为这A是我们看到的类型。

With that information, let's consider the other types.

有了这些信息，让我们考虑其他类型。

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

map (_._2):
B = String

We can see that the type returned by the first mapis Map[Int,Int], and the second is Iterable[String]. Looking at map's definition, it is easy to see that these are the values of That. But where do they come from?

我们可以看到第一个返回的类型map是Map[Int,Int]，第二个是Iterable[String]。查看map的定义，很容易看出这些是 的值That。但它们来自哪里？

If we look inside the companion objects of the classes involved, we see some implicit declarations providing them. On object Map:

如果我们查看所涉及类的伴随对象，我们会看到一些提供它们的隐式声明。在对象上Map：

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

And on object Iterable, whose class is extended by Map:

在 object 上Iterable，其类扩展为Map：

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

These definitions provide factories for parameterized CanBuildFrom.

这些定义为参数化提供了工厂CanBuildFrom。

Scala will choose the most specific implicit available. In the first case, it was the first CanBuildFrom. In the second case, as the first did not match, it chose the second CanBuildFrom.

Scala 将选择最具体的隐式可用。在第一种情况下，它是第一个CanBuildFrom. 在第二种情况下，由于第一个不匹配，它选择了第二个CanBuildFrom。

Back to the Question

回到问题

Let's see the code for the question, List's and map's definition (again) to see how the types are inferred:

让我们看一下问题的代码，List's 和map's 定义（再次）以了解如何推断类型：

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 

The type of List("London", "Paris")is List[String], so the types Aand Reprdefined on TraversableLikeare:

的类型List("London", "Paris")是List[String]，所以类型A和Repr定义TraversableLike是：

A = String
Repr = List[String]

The type for (x => (x.length, x))is (String) => (Int, String), so the type of Bis:

的类型(x => (x.length, x))是(String) => (Int, String)，所以类型B是：

B = (Int, String)

The last unknown type, Thatis the type of the result of map, and we already have that as well:

最后一个未知类型，That是 的结果类型map，我们也已经有了：

val map : Map[Int,String] =

So,

所以，

That = Map[Int, String]

That means breakOutmust, necessarily, return a type or subtype of CanBuildFrom[List[String], (Int, String), Map[Int, String]].

这意味着breakOut必须必须返回 的类型或子类型CanBuildFrom[List[String], (Int, String), Map[Int, String]]。

回答by Austen Holmes

I'd like to build upon Daniel's answer. It was very thorough, but as noted in the comments, it doesn't explain what breakout does.

我想以丹尼尔的回答为基础。这是非常彻底的，但正如评论中所指出的，它没有解释突破的作用。

Taken from Re: Support for explicit Builders(2009-10-23), here is what I believe breakout does:

摘自Re: Support for explicit Builders(2009-10-23)，这是我认为突破所做的：

It gives the compiler a suggestion as to which Builder to choose implicitly (essentially it allows the compiler to choose which factory it thinks fits the situation best.)

它为编译器提供了一个关于隐式选择哪个 Builder 的建议（本质上它允许编译器选择它认为最适合情况的工厂。）

For example, see the following:

例如，请参阅以下内容：

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)

You can see the return type is implicitly chosen by the compiler to best match the expected type. Depending on how you declare the receiving variable, you get different results.

您可以看到编译器隐式选择返回类型以最佳匹配预期类型。根据您声明接收变量的方式，您会得到不同的结果。

The following would be an equivalent way to specify a builder. Note in this case, the compiler will infer the expected type based on the builder's type:

以下是指定构建器的等效方法。请注意，在这种情况下，编译器将根据构建器的类型推断预期类型：

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)

回答by Dzhu

Daniel Sobral's answer is great, and should be read together with Architecture of Scala Collections(Chapter 25 of Programming in Scala).

Daniel Sobral 的回答很棒，应该与Architecture of Scala Collections（Programming in Scala 的第 25 章）一起阅读。

I just wanted to elaborate on why it is called breakOut:

我只是想详细说明为什么叫它breakOut：

Why is it called breakOut?

为什么叫它breakOut？

Because we want to break out of one type and into another:

因为我们想突破一种类型并进入另一种类型：

Break out of what type into what type? Lets look at the mapfunction on Seqas an example:

突破什么类型变成什么类型​​？让我们以mapon 函数Seq为例：

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

If we wanted to build a Map directly from mapping over the elements of a sequence such as:

如果我们想直接通过对序列元素进行映射来构建 Map，例如：

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

The compiler would complain:

编译器会抱怨：

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

The reason being that Seq only knows how to build another Seq (i.e. there is an implicit CanBuildFrom[Seq[_], B, Seq[B]]builder factory available, but there is NObuilder factory from Seq to Map).

原因是，SEQ只知道如何建造另一个序列（即有一个隐含的CanBuildFrom[Seq[_], B, Seq[B]]建设者工厂提供，但NO生成器工厂从SEQ到地图）。

In order to compile, we need to somehow breakOutof the type requirement, and be able to construct a builder that produces a Map for the mapfunction to use.

为了编译，我们需要以某种方式breakOut满足类型需求，并且能够构造一个生成器来生成供map函数使用的 Map 。

As Daniel has explained, breakOut has the following signature:

正如 Daniel 所解释的，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()
    }

Nothingis a subclass of all classes, so any builder factory can be substituted in place of implicit b: CanBuildFrom[Nothing, T, To]. If we used the breakOut function to provide the implicit parameter:

Nothing是所有类的子类，因此任何构建器工厂都可以代替implicit b: CanBuildFrom[Nothing, T, To]. 如果我们使用 breakOut 函数提供隐式参数：

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

It would compile, because breakOutis able to provide the required type of CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]], while the compiler is able to find an implicit builder factory of type CanBuildFrom[Map[_, _], (A, B), Map[A, B]], in place of CanBuildFrom[Nothing, T, To], for breakOut to use to create the actual builder.

它会编译，因为breakOut能够提供所需的 类型CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]]，而编译器能够找到类型为 的隐式构建器工厂CanBuildFrom[Map[_, _], (A, B), Map[A, B]]，而不是CanBuildFrom[Nothing, T, To]，以便 breakOut 用于创建实际的构建器。

Note that CanBuildFrom[Map[_, _], (A, B), Map[A, B]]is defined in Map, and simply initiates a MapBuilderwhich uses an underlying Map.

请注意，CanBuildFrom[Map[_, _], (A, B), Map[A, B]]在 Map 中定义，并简单地启动MapBuilder使用底层 Map 的 a。

Hope this clears things up.

希望这能解决问题。

回答by fdietze

A simple example to understand what breakOutdoes:

一个简单的例子来理解什么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]