map函数,隐式参数CanBuildFrom的细节

在twitter上看到过的:http://www.dotkam.com/2012/05/08/scala-fun-with-canbuildfrom/
《快学Scala》这本书的p333页有对CanBuildFrom这个隐式参数的解读。

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this)
    for (x <- this) b += f(x)
    b.result
}

先要弄清楚Repr这个类型参数的含义:意思是“展现类型”?
还有Builder这个trait,里面定义了+=和result两个方法。

//2013.2.19 补充,从下面这个例子分析

"abc".map(_+1) 
$ scala -Xprint:typer -e "\"abc\".map(_+1)" 

这句表达式被翻译为StringOps.map(...) ,除了显式传入的 Char => Int 的函数,后边还有个隐式的参数:(scala.this.Predef.fallbackStringCanBuildFrom[Int])

看了一下 Predef里面,没有找到 fallbackStringCanBuildFrom ,倒是发现了
DummyImplicit 这个类,注释里有提到: @see scala.Array$, method `fallbackCanBuildFrom`
Array的伴生对象确实继承了 FallbackArrayBuilding这个类,它里面有个隐式转换方法:

implicit def fallbackCanBuildFrom[T](implicit m: DummyImplicit): CanBuildFrom[Array[_], T, ArraySeq[T]] =
    new CanBuildFrom[Array[_], T, ArraySeq[T]] {
    def apply(from: Array[_]) = ArraySeq.newBuilder[T]
    def apply() = ArraySeq.newBuilder[T]
}

// 继续,通过断点跟踪了一下,是在 LowPriorityImplicits 这个class里定义了一些隐式转换函数,跟上面的无关。

implicit def fallbackStringCanBuildFrom[T]: CanBuildFrom[String, T, immutable.IndexedSeq[T]] =
    new CanBuildFrom[String, T, immutable.IndexedSeq[T]] {
    def apply(from: String) = immutable.IndexedSeq.newBuilder[T]
    def apply() = immutable.IndexedSeq.newBuilder[T]
}

见下图:

而map方法是在 TraversableLike 这个trait里定义的:

把断点设置在上面的 val b = bf(repr) 这一行,先看看repr这个变量在TraversableLike里的定义,是一个函数,返回自身对象,造型为Repr类型。

/** The collection of type $coll underlying this `TraversableLike` object.  
*  By default this is implemented as the `TraversableLike` object itself,  
*  but this can be overridden.  
*/
def repr: Repr = this.asInstanceOf[Repr]

对于String来说,这个repr就是自身,bf(repr) 调用 CanBuildFrom.apply 方法,而fallbackStringCanBuildFrom提供的builder是
Builder[A,IndexedSeq[A]] 类型,它的实现实际是 VectorBuilder,见 IndexedSeq类的伴生对象。

每个集合都在其伴生对象里提供了一个隐式的CanBuildFrom对象。

builder创建好了目标类型的容器后,开始迭代当前容器执行f函数转换,并将结果填入目标容器。

for(x <- this) b+= f(x)

这个for表达式转化为 StringOps.foreach(f:A=>B),实际调用的是 IndexedSeqOptimized.foreach(f:A=>B)
里的逻辑,这个 foreach(func) 是override了 IterableLike 里的foreach方法。

VectorBuilder的result返回的是Vector类型,它也混入了IndexedSeq特质

scala> "abc".map(_+1)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(98, 99, 100)

整个来龙去脉弄清楚了。另外,Vector是树形数组,效率比较高。

发表评论

电子邮件地址不会被公开。 必填项已用*标注