Scala 2.8 breakOut

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使用a 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转换每个元素的情况下),并将结果存储在新集合中.

为了最大化代码重用,结果的存储是通过builder(scala.collection.mutable.Builder)完成的,它基本上支持两个操作:追加元素,并返回结果集合.此结果集合的类型取决于构建器的类型.因此,List构建器将返回a List,Map构建器将返回a Map,依此类推.该map方法的实现不需要关注结果的类型:构建器负责处理它.

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

Builder通过这种CanBuildFrom隐式来执行从已知类型的表达式中产生最佳可能性的魔力.

关于 CanBuildFrom

为了更好地解释发生了什么,我将给出一个示例,其中映射的集合是a Map而不是a List.我会回到List以后的.现在,请考虑以下两个表达式:

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

第一个返回a Map,第二个返回a 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))is (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]].

Answer 2

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

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

Answer 3

Daniel Sobral的答案很棒,应该与Scala集合体系结构(Scala编程的第25章)一起阅读.

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

为什么叫它breakOut？

因为我们想要突破一种类型而不是另一种类型:

突破什么类型成什么类型​​？让我们看看map函数Seq作为一个例子:

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只知道如何建造另一个序列(即有一个隐含的CanBuildFrom[Seq[_], B, Seq[B]]建设者工厂提供,但NO生成器工厂从SEQ到地图).

为了编译,我们需要某种breakOut类型的需求,并能够构造一个构建器,为map要使用的函数生成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是所有类的子类,因此可以替换任何构建器工厂来代替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]]是在Map中定义的,只是启动一个MapBuilder使用底层Map的a.

希望这可以解决问题.

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]