Scala 2.8 突破

Question

在 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？

Answer 1

答案可以在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并将结果直接收集到地图？显然，是的，确实如此。然而，要做到这一点，我们需要将正确的 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 （它返回一个 可迭代）。

从表达式的已知类型生成最佳的 Builder 的魔力是通过此 CanBuildFrom 隐式执行的。

关于 CanBuildFrom

为了更好地解释发生的情况，我将给出一个示例，其中映射的集合是 Map 而不是 列表。稍后我会返回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)) => 类型的函数字符串。我使用双括号来强调它是接收到的元组，因为这是我们看到的 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 和 TraversableLike 上定义的 Repr 为：

A = String
Repr = List[String]

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

B = (Int, String)

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

val map : Map[Int,String] =

所以，

That = Map[Int, String]

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

Answer 2

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

摘自回复：对显式构建器的支持 (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)

Answer 3

Daniel Sobral 的回答很棒，应该与 Architecture 一起阅读Scala 集合（《Scala 编程》第 25 章）。

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

为什么叫breakOut？

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

从什么类型突破到什么类型？让我们以 Seq 上的 map 函数为例：

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

如果我们想直接通过映射序列的元素来构建一个 Map，例如：

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]] 构建器工厂可用，但没有 构建器工厂（从 Seq 到 Map）。

为了编译，我们需要以某种方式breakOut类型要求，并能够构造一个生成器，为<要使用的 code>map 函数。

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

Nothing 是所有类的子类，因此任何构建器工厂都可以替换隐式 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]] 是在 Map 中定义的，并且只需启动一个 MapBuilder 即可使用底层地图。

希望这能解决问题。

Answer 4

通过一个简单的例子来了解 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]