Scala 2.8 突破 [英] Scala 2.8 breakOut

问题描述

在Scala 2.8中，scala.collection.package.scala中有一个对象:

In Scala 2.8, there is an object in 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?

What is going on here? Why is breakOut being called as an argument to my List?

推荐答案

答案在map的定义上找到:

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

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

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 specific one available.

关于breakOut

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

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 Map out of it. The most obvious way to do that would produce an intermediary List[(Int, String)] collection, and then convert it.

鉴于 map 使用 Builder 生成结果集合，是否可以跳过中间 List 并收集结果直接转化为Map?显然，是的，确实如此.但是，要做到这一点，我们需要将适当的 CanBuildFrom 传递给 map，而这正是 breakOut 所做的.

Given that map uses a Builder to produce the resulting collection, wouldn't it be possible to skip the intermediary List and collect the results directly into a Map? Evidently, yes, it is. To do so, however, we need to pass a proper CanBuildFrom to map, and that is exactly what breakOut does.

接下来我们看一下breakOut的定义:

Let's look, then, at the definition of 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]].因此:

Note that breakOut is parameterized, and that it returns an instance of CanBuildFrom. As it happens, the types From, T and To have already been inferred, because we know that map is expecting CanBuildFrom[List[String], (Int, String), Map[Int, String]]. Therefore:

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

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

To conclude let's examine the implicit received by breakOut itself. 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?

我们来看看CanBuildFrom的定义:

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

所以 CanBuildFrom 在它的第一个类型参数上是逆变的.因为Nothing 是底层类(即它是一切的子类)，这意味着any 类可以用来代替Nothing.

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

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

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

关于构建器

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

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.

为了最大限度地重用代码，这种结果的存储是通过一个 builder (scala.collection.mutable.Builder) 完成的，它基本上支持两种操作:附加元素，并返回结果集合.此结果集合的类型将取决于构建器的类型.因此，List 构建器将返回一个 List，Map 构建器将返回一个 Map，依此类推.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 List builder will return a List, a Map builder will return a Map, and so on. The implementation of the map method need not concern itself with the type of the result: the builder takes care of it.

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

On the other hand, that means that map needs 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).

从已知类型的表达式中生成尽可能最好的 Builder 的魔法是通过这个 CanBuildFrom 隐式执行的.

The magic of producing the best possible Builder from the known types of the expression is performed through this CanBuildFrom implicit.

关于CanBuildFrom

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

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

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

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

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

方法map 继承自TraversableLike.它在 B 和 That 上参数化，并利用了类型参数 A 和 Repr，它们参数化了班级.让我们一起看看这两个定义:

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

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 本身的定义:

To understand where A and Repr come from, let's consider the definition of Map itself:

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

因为 TraversableLike 被所有扩展 Map 的 trait 继承，A 和 Repr 可以从任何继承其中.不过，最后一个获得了偏好.因此，按照不可变的 Map 的定义以及将它连接到 TraversableLike 的所有特征，我们有:

Because TraversableLike is inherited by all traits which extend Map, A and Repr could be inherited from any of them. The last one gets the preference, though. So, following the definition of the immutable Map and all the traits that connect it to TraversableLike, we have:

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 使用的是:

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:

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

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

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 A as we saw.

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

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

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

map (_._2):
B = String

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

We can see that the type returned by the first map is 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 上:

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

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

在对象Iterable上，其类被Map扩展:

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

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

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

These definitions provide factories for parameterized CanBuildFrom.

Scala 将选择最具体的隐式可用.在第一种情况下，它是第一个 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.

回到问题

让我们看看问题的代码，List 和 map 的定义(再次)看看如何推断类型:

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

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 和 TraversableLike 上定义的 >Repr 是:

The type of List("London", "Paris") is List[String], so the types A and Repr defined on TraversableLike are:

A = String
Repr = List[String]

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

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

B = (Int, String)

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

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

val map : Map[Int,String] =

所以，

That = Map[Int, String]

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

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

这篇关于Scala 2.8 突破的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！