理解 CanBuildFrom

概述

Scala 2.8 发布了新的集合库,其中大量利用了 canBuildFrom 隐式转换;Scala 2.12 发布之后,官方宣布重新设计集合库,其中一个目标就是移除 canBuildFrom 设计。在本文中,我们会了解到 canBuildFrom 解决的问题以及新的集合库替代解决方法。

转换集合元素

我们可以将 String 看作是 Char 元素的集合,这样就可以对 String 使用 ++, find 等操作。但是这么做又会给 map 实现带来挑战,因为 map 有可能将 Char 转化成非 Char 的值。我们希望的是:如果 map 将 Char 转换为另一个 Char,那么应该返回一个 String;如果 map 将 Char 转换成另一种类型 B,那么应该返回 Seq[B]。事实上,这也是当前集合库的实现方案:

scala> "foo".map( _.toInt)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(102, 111, 111)

scala> "foo".map(_.toUpper)
res1: String = FOO

不只是 map 方法,flatMap,collect,concat 和其他一些方法也有相同特性。此外,其他集合如 BitSet 和 map 等也需要这样的特性。

当前集合库依赖 CanBuildFrom 实现这样的特性,CanBuildFrom 是一个 trait,声明为:

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

类型参数 From,Elem,To 定义为:

  • From the type of the underlying collection that requests a builder to be created.
  • Elem the element type of the collection to be created.
  • To the type of the collection to be created.

对于 String,map 方法定义如下:

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

CanBuildFrom 会修复返回类型:如果 B 是 Char,那么 That 就会是 String 类型;否则 That 就是 immutable.IndexedSeq 类型。

在新集合库中,设计者们通过定义两个重载 map 方法:一个处理 Char 到 Char 的转换;另一个处理其他类型的转换。这两个 map 方法定义如下:

def map(f: Char => Char): String
def map[B](f: Char => B): Seq[B]

这样的话,如果我们向 map 传递一个返回 Char 类型的函数,那么编译器就会选择第一个 map 方法;否则选择第二个 map 方法。在 Scala 2.12 之前,这样的设计比较笨拙:用户必须显式写出函数 f 的类型参数。Scala 2.12 改进了类型推导,避免了这种窘况。

集合的类型构造函数具有不同特征

Scala 集合库按照层次化组织,最上层的是 Iterable[A],有三个子类继承 Iterable[A],分别是:Seq[A],Set[A] 和 Map[K,V],见下图:

注意到 Map[K, V] 接受两个类型参数(K 和 V)而其他集合类型只接受一个类型参数。这样的话,我们很难在 Iterable[A] 中定义能够返回 Map[K, V] 的泛型操作。

比如考虑 map 方法,我们可能希望将 map 定义在 Iterable[A] 中,但是问题是 map 返回类型应该是什么呢?当 map 方法被 List[A] 继承时,我们希望方法返回类型是 List[B];而当 map 方法被 HashMap[K, V] 继承时,我们希望方法返回类型是 HashMap[L, W]。

当前集合库通过 CanBuildFrom 解决这个问题。在 Iterable[A] 中 map 方法定义如下(Scala 2.12 中,map 定义移到了 TraversableLike):

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

返回类型 That 是在调用方通过 CanBuildFrom 推导得到:当 Repr 是 List[_],那么 That 固定为 List[B];当 Repr 是 HashMap[_,_] 并且 B 是元组 (K, V),那么 That 固定为 HashMap[K,V]。

在新集合库中,设计者们通过定义两个”分之”来解决这个问题:

  • IterableOps 适用于类型构造器接受一个参数的集合
  • MapOps 适用于类型构造器接受两个参数的集合

下面是简化版的 IterableOps 定义:

trait IterableOps[A, CC[_]] {
  def map[B](f: A => B): CC[B]
}

类型参数 CC 代表 Collection type Constructor。这样,List[A] 实际继承 ItertableOps[A, List]。

下面是简化版的 MapOps 定义:

trait MapOps[K, V, CC[_, _]] extends IterableOps[(K, V), Iterable] {
  def map[L, W](f: ((K, V)) => (L, W)): CC[L, W]
}

这样,HashMap[K, V] 实际继承 MapOps[K, V, HashMap]。注意 MapOps 继承 IterableOps,这样 MapOps 就有两个重载 map 方法。

有序集合

有序集合需要一个有序关系来定义元素之间的顺序。如果要使用 map 对有序集合中的元素做转换,那么新的元素类型必须存在一个隐式有序关系。目前集合库的解决方法还是依赖隐式转换机制,即 CanBuildFrom:比如对于类型 X,只有当存在隐式关系 Ordering[X],那么才存在 CanBuildFrom[TreeSet[_], X, TreeSet[X]]。

而在新集合库中,设计者们同样通过引入一个新的分支解决,即定义一个需要排序实例的转换操作:

trait SortedIterableOps[A, CC[_]] {
  def map[B : Ordering](f: A => B): CC[B]
}

如果我们抽象出这几种操作,那么我们就可以得到如下四个分支:

种类 无序 有序
CC[_] IterableOps SortedIterableOps
CC[_, _] MapOps SortedMapOps

breakOut

breakOut 是另一个利用 CanBuildFrom 的设计。考虑下面的程序:

val xs: List[Int] = 1 :: 2 :: 3 :: Nil
val xsWithSquares: Map[Int, Int] =
  xs.map(x => (x, x * x))

如果我们编译上述代码那么会得到一个编译错误,这是因为 map 的结果是 List[(Int,Int)] 而不是 Map[Int,Int]。解决方法是使用 breakOut:

val xs: List[Int] = 1 :: 2 :: 3 :: Nil
val xsWithSquares: Map[Int, Int] =
  xs.map(x => (x, x * x))(collection.breakOut)

breakOut 可以理解为 break out of one type and into another,会自动选择合适的 CanBuildFrom 实例而无需考虑原集合类型。breakOut 要求目标类型已知,上述情况就是通过显式类型声明。

新集合库没有 breakOut 的直接等价物,那么上述例子的解决方法是使用一个 View 避免创建中间集合:

val xs: List[Int] = 1 :: 2 :: 3 :: Nil
val xsWithSquares: Map[Int, Int] =
  xs.view.map(x => (x, x * x)).to(Map)

总结

CanBuildFrom 能有效的帮助 Scala 集合库实现 same-result-type 原则,但是又比较”异类”,以致于 Scala 官方在文档中省略了该参数说明。不过 Scala 2.12 改进了类型推导,这样在新集合库中,设计者们可以定义多个重载方法,如多个 map 方法,而不需要再依赖 CanBuildFrom。这样做的好处是我们可以通过方法的类型参数立即知道该方法的作用,而不需要关心隐式转换了。

参考

  1. Tribulations of CanBuildFrom | The Scala Programming Language

Previous post: LeetCode Reservoir Sampling 问题总结

Next post: Scala 中的 Monads