Scala集合精粹

2016-08-10 本文已影响695人刘光聪

Controlling complexity is the essence of computer programming. -- Brian Kernigan.

当我第一次阅读Scala集合框架源代码时，众多的特质，类型参数，隐式参数，类型约束扑朔迷离，很难摸清框架设计的精髓。

例如TraversableLike.map方法声明：

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

Repr的类型参数代表什么含义？CanBuildFrom类型的「隐式参数」有什么用途？其隐式值在哪里定义的？如此复杂的设计会有什么样的收益？

本文通过对Scala集合框架的几个设计要点进行剖析，以便揭示其内在的设计精髓。

关键抽象

事实上，Scala集合框架是一份难得的设计佳作，将其「正交设计」做到了极致。Scala集合框架通过抽象出两个最本质的「变化方向」，从而消除各个容器算子的重复代码。

****构建器****：使用统一的构建过程，而无需关心容器的表示；
****迭代器****：使用统一的遍历过程，而无需关心容器的表示；

迭代器

其中，foreach抽象方法，及其Iterator特质分别提供了「内部迭代器」和「外部迭代器」的抽象。

trait TraversableLike[+A, +Repr] {
  def foreach[U](f: A => U): Unit
  ...
}

trait Iterator[+A] {
  def hasNext: Boolean
  def next(): A
  ...
}

后文将再次重点介绍foreach，及其Iterator的工作原理，及其使用场景。

构建器

Builder特质提供了「构建器」的抽象，将「容器的构建过程与表示分离」。针对不同的容器类型定制不同的Builder，实现容器的构建过程的复用。

Builder[-Elem, +To]是用于构建To[Elem]类型容器的抽象，它的工作原理类似于缓冲区。

通过+=向缓存追加元素，最终通过result返回To[Elem]类型容器的实例；调用result之后，Builder变为无效；如果调用clear，则Builder又可以再次启用构建的功能。

package scala.collection.mutable

trait Builder[-Elem, +To] {
  def +=(elem: Elem): this.type
  def result(): To
  def clear(): Unit
  ...
}

其中，Scala集合框架提供了两种创建Builder实例的多态工厂方法，一种使用继承的多态，另外一种使用「类型类(typeclass)」的多态。

模板方法：def newBuilder: Builder[Elem, Repr]
隐式参数：implicit bf: CanBuildFrom[Repr, B, That]

消除重复

针对于Seq[T], Set[T], Map[K, V]等多种形态的容器类型，即使其类型参数的数目不一样，如何在系统中存在唯一的filter实现呢？

模板方法

事实上，Scala集合框架在TraversableLike唯一地实现了filter操作，实现各容器间的代码复用。

除非有特殊的性能限制，对于普通容器实现，可以通过Mixin这个特质即可免费地得到filter的默认实现。

其中，newBuilder多态创建了一个Builder实例，并依赖于抽象的foreach方法迭代地实现filter操作。

这是模板方法的典型运用；特殊地，newBuilder同时是一个工厂方法。

trait TraversableLike[+A, +Repr] {
  def newBuilder: Builder[A, Repr]
  def foreach[U](f: A => U): Unit

  def filter(p: A => Boolean): Repr = {
    val b = newBuilder
    foreach { elem => if (p(elem)) b += elem }
    b.result
  }
  ...
}

胖接口

通过依赖于抽象的foreach, newBuilder方法，可方便地提供其他算子的默认实现，这也是Scala社区倡导「胖接口」设计的一个经典案例。

Java社区更倾向于「瘦接口」设计；而Scala社区与之相反，这归功于trait的优秀特性。具有讽刺的是，自Java8开始支持Default Method后，「胖接口」的接口设计风格开始逐渐流行起来了。

trait TraversableLike[+A, +Repr] {
  def newBuilder: Builder[A, Repr]
  def foreach[U](f: A => U): Unit

  def filter(p: A => Boolean): Repr = {
    val b = newBuilder
    foreach { elem => if (p(elem)) b += elem }
    b.result
  } 
  
  def partition(p: A => Boolean): (Repr, Repr) = {
    val l, r = newBuilder
    for (x <- this) (if (p(x)) l else r) += x
    (l.result, r.result)
  }
  ...
}

目标集合

Scala集合框架遵循「结果类型相同」的原则；也就是说，Map调用filter操作后返回Map；Set调用filter操作后返回Set，这符合常人的习惯思维。

但在实现技术上，如何保证Seq, Set, Map，甚至Array, String的filter没有重复，而又要遵循「结果类型相同」的原则呢？

Scala集合框架引入了Like的特质，例如Traversable通过将「自身的类型信息」注入给TraversableLike的Repr类型参数；它不仅持有容器元素类型信息，而且持有「容器的表示类型」。

trait Traversable[+A] extends TraversableLike[A, Traversable[A]]

事实上，Repr表示Builder, CanBuildFrom待构建「目标容器类型」，从而TraversableLike可以方便地做到目标容器的构建。

因为TraversableLike实现了Traversable大部分算子，因此TraversableLike常常被称为Traversable的「实现特质」。

结果类型相同

依赖于newBuilder的多态工厂方法，使得容器操作算子后，「容器类型」，「容器元素类型」都将保持不变，例如filter算子。

trait TraversableLike[+A, +Repr] {
  def newBuilder: Builder[A, Repr]
  def foreach[U](f: A => U): Unit
          ...
  def filter(p: A => Boolean): Repr = {
    val b = newBuilder
    foreach { elem => if (p(elem)) b += elem }
    b.result
  }
}

结果类型不同

当操作map操作时，「容器类型」，或「容器元素类型」可能发生变化，可以通过定制CanBuildFrom[Repr, B, That]的「类型类」来实现多态构造。

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

其中，bf(repr)通过调用CanBuildFrom.apply方法，多态地创建了一个Builder实例。

CanBuildFrom

事实上，CanBuildFrom是Builder的工厂方法，用于多态创建Builder实例。它表示From[A] -> To[B]的创建过程，即从集合From[A]到集合To[B]构建器的多态创建。

trait CanBuildFrom[-From, -B, +To] {
  def apply(from: From): Builder[B, To]
}

隐式值

如何找到map算子中bf的隐式值呢？根据隐式值查找规则，及其习惯用法，隐式值出现于容器的伴生对象中。

import scala.collection.immutable.BitSet

val bits = BitSet(1, 2, 3)

如果map的目标集合元素类型是Int：

// scala.collection.immutable.BitSet = BitSet(2, 4, 6)  
bits map (_ * 2)

使用BitSet伴生对象中的隐式值：

object BitSet {
  implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = ???
}

如果map的目标集合元素类型不是Int：

// scala.collection.immutable.SortedSet[Float] = TreeSet(1.0, 2.0, 3.0)
bits map (_.toFloat)

则使用BitSet的父类SortedSet的伴生对象中的隐式值：

implicit def newCanBuildFrom[A](implicit ord : Ordering[A]) = 
  new CanBuildFrom[CC[_], A, CC[A]] {
    def apply(from: CC[_]) = newBuilder[A](ord)
  }
  
def newBuilder[A](implicit ord: Ordering[A]): Builder[A, CC[A]] = ???

其中，CC在此例被实例化为SortedSet，A实例化为Float。