CanBuildFrom is probably the most infamous abstraction of the current collections. It is mainly criticised for making scary type signatures.

上一篇文章 看出, CanBuildFrom 在当前 Scala 集合库中扮演了最关键的角色。而它,也如引言所道,又是其中最具争议的设计。

本文将详细介绍 CanBuildFrom 的特性,它为何饱受诟病,而又解决了哪些问题。

map 的定义

以下是马丁在 Scala – the Simple Parts talk 中 PPT 的一页:


type of map is ugly

我们来看下 map 的类型到底有多丑?

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

如果你接触 Scala 不深,以上的 implicit 的确费解。其实它无非是在 Scala 中实现 Type class 的一种方式,这里你可以简单理解为:如此 map 就会在隐式范围中自动寻找关于 bf 对象的实现

为什么要采用这种方式呢?我们说过,CanBuildFrom 是极其强大的,以下是它解决的三大问题。

一、集合类型变换

map 最常见的操作,就是对集合中的元素进行转化,例如:

1
2
3
List(1, 2, 3).map(_.toString) // List[String] = List(1, 2, 3)
"foo".map(c => c.toUpper) // String = FOO
"foo".map(c => c.toInt) // scala.collection.immutable.IndexedSeq[Int] = Vector(102, 111, 111)

这里,一个 String 可被视为 Char 元素的集合,它如同其它集合一样,在被 map 之后,有两种情况:

  • 类型不变,还是返回一个 String
  • 类型变了,返回一个 scala.collection.immutable.IndexedSeq[Int]

这是 CanBuildFrom 要解决的第一个问题 — 对要 map 的集合进行「类型修改」

还记得 CanBuildFrom 的定义吗?

1
2
3
4
trait CanBuildFrom[-From, -Elem, +To] {
// 创建一个新的构造器(builder)
def apply(from: From): Builder[Elem, To]
}

复习下:「有这么一个方法,由给定的 From 类型的集合,使用 Elem 类型,建立 To 类型的集合」

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

我们把类型参数 Elem 替换成 CharFrom 替换为 String,如此便实现了 String 类型的 map 操作。

二、不同的集合类型参数

我们知道,Seq[A]Set[A] 继承了 Iterable[A],三者有个相同点 — 都有一个类型参数。然而 Map[K, V] 是个特例,它也继承了 Iterable[A],但却拥有两个。

这就带来了一个问题。如果 List[A] 继承了 Iterable[A] 中的 map ,需要一个返回类型 List[B],然而对 HashMap[K, V] 操作,却期望返回 HashMap[L, W]这里的类型参数数量出现了不一致的情况

CanBuildFrom 再一次化解了这个问题。

  • ReprList[_] 时,That 变成了 List[B]
  • ReprHashMap[_, _] 时,B 就是元祖 (K, V),而 That 变成了 HashMap[K, V]

三、有序集合的排序问题

思考有序集合之间的元素转换问题,比如 TreeSet。它们任何一次 map操作,都需要能够对元素进行排序,那么这种元素间的排序关系如何被定义呢?

同样是定义一个 CanBuildFrom 的隐式对象,它的类型为 CanBuildFrom[TreeSet[_], X, TreeSet[X]]。其中 X 代表集合元素的类型,于是我们就可以利用相同的技术,定义一个 Ordering[X] 隐式对象,它解释了如何对 TreeSet 的元素进行排序。

Simple is not Easy

上面列举了 CanBuildFrom 的各种美好,然而它还是逃脱不了被新方案替代的命运。究其原因,也可以用马丁 talk 的另一页 PPT 解释,Simple != Easy 。相信这也是 Scala 在「学院」与「工业」之间做出的平衡选择。


simple is not easy

参考