scala - 如何将“丰富我的图书馆”模式应用于Scala集合？

Question

Scala中可用的最强大的模式之一是rich-my-library *模式，该模式使用隐式转换来显示将方法添加到现有类中，而无需动态方法解析。例如，如果我们希望所有字符串都具有方法spaces来计算它们具有多少空白字符，我们可以:

class SpaceCounter(s: String) {
  def spaces = s.count(_.isWhitespace)
}
implicit def string_counts_spaces(s: String) = new SpaceCounter(s)

scala> "How many spaces do I have?".spaces
res1: Int = 5

不幸的是，这种模式在处理通用集合时会遇到麻烦。例如，有人询问了有关grouping items sequentially with collections的许多问题。没有内置功能可以一次性完成，因此这似乎是使用通用集合C和通用元素类型A的“丰富我的图书馆”模式的理想选择:

class SequentiallyGroupingCollection[A, C[A] <: Seq[A]](ca: C[A]) {
  def groupIdentical: C[C[A]] = {
    if (ca.isEmpty) C.empty[C[A]]
    else {
      val first = ca.head
      val (same,rest) = ca.span(_ == first)
      same +: (new SequentiallyGroupingCollection(rest)).groupIdentical
    }
  }
}

当然，这是行不通的。 REPL告诉我们:

<console>:12: error: not found: value C
               if (ca.isEmpty) C.empty[C[A]]
                               ^
<console>:16: error: type mismatch;
 found   : Seq[Seq[A]]
 required: C[C[A]]
                 same +: (new SequentiallyGroupingCollection(rest)).groupIdentical
                      ^

有两个问题:如何从空的C[C[A]]列表(或凭空获取)获得C[A]？以及如何从C[C[A]]行取回same +:而不是Seq[Seq[A]]？

*前身为皮条客我的图书馆。

Answer 1

理解此问题的关键是要意识到，有两种不同的方法可以在集合库中构建和使用集合。一种是 public 收藏夹接口(interface)及其所有不错的方法。另一个是构建器，它广泛用于创建集合库，但几乎从未在其外部使用。

我们的富集问题与集合库本身在尝试返回相同类型的集合时面临的问题完全相同。也就是说，我们要构建集合，但是在常规工作时，我们没有办法引用“与集合已经存在的相同类型”。因此，我们需要建造者。

现在的问题是:我们从哪里得到建造者？明显的地方是来自收藏本身。这行不通。在转到通用集合时，我们已经决定要忘记集合的类型。因此，即使该集合可以返回一个生成器，该生成器将生成我们想要的类型的更多集合，但它也不知道类型是什么。

相反，我们从 float 的CanBuildFrom隐式获取构建器。这些是专门为匹配输入和输出类型并为您提供适当类型的构建器而存在的。

因此，我们有两个概念上的飞跃:

我们没有使用标准的集合操作，我们正在使用构建器。

我们从隐式CanBuildFrom而不是直接从我们的集合中获得这些构建器。

让我们来看一个例子。

class GroupingCollection[A, C[A] <: Iterable[A]](ca: C[A]) {
  import collection.generic.CanBuildFrom
  def groupedWhile(p: (A,A) => Boolean)(
    implicit cbfcc: CanBuildFrom[C[A],C[A],C[C[A]]], cbfc: CanBuildFrom[C[A],A,C[A]]
  ): C[C[A]] = {
    val it = ca.iterator
    val cca = cbfcc()
    if (!it.hasNext) cca.result
    else {
      val as = cbfc()
      var olda = it.next
      as += olda
      while (it.hasNext) {
        val a = it.next
        if (p(olda,a)) as += a
        else { cca += as.result; as.clear; as += a }
        olda = a
      }
      cca += as.result
    }
    cca.result
  }
}
implicit def iterable_has_grouping[A, C[A] <: Iterable[A]](ca: C[A]) = {
  new GroupingCollection[A,C](ca)
}

让我们分开。首先，为了构建集合的集合，我们知道我们需要构建两种类型的集合:每个组的C[A]和将所有组聚集在一起的C[C[A]]。因此，我们需要两个构建器，一个使用A并构建C[A]，另一个使用C[A]并构建C[C[A]]。查看CanBuildFrom的类型签名，我们看到

CanBuildFrom[-From, -Elem, +To]

这意味着CanBuildFrom想要知道我们开始的集合的类型-在我们的例子中是C[A]，然后是生成的集合的元素和该集合的类型。因此，我们将它们作为隐式参数cbfcc和cbfc填写。

意识到这一点，这就是大部分工作。我们可以使用CanBuildFrom来为我们提供构建器(您需要做的就是应用它们)。并且，一个构建器可以使用+=建立一个集合，将其转换为最终应该使用result生成的集合，然后清空自身并准备使用clear重新开始。构建器开始是空的，这解决了我们的第一个编译错误，并且由于我们使用构建器而不是递归，因此第二个错误也消失了。

最后一个小细节-除了实际工作的算法之外-隐式转换。请注意，我们使用的是new GroupingCollection[A,C]而不是[A,C[A]]。这是因为类声明是针对带有一个参数的C的，它使用传递给它的A自身填充了它。因此，我们只将其类型为C，然后让其创建C[A]即可。较小的细节，但是如果尝试另一种方法，则会出现编译时错误。

在这里，我使该方法比“相等元素”集合更为通用-相反，只要对顺序元素的测试失败，该方法就会将原始集合切开。

让我们看看我们的方法在起作用:

scala> List(1,2,2,2,3,4,4,4,5,5,1,1,1,2).groupedWhile(_ == _)
res0: List[List[Int]] = List(List(1), List(2, 2, 2), List(3), List(4, 4, 4), 
                             List(5, 5), List(1, 1, 1), List(2))

scala> Vector(1,2,3,4,1,2,3,1,2,1).groupedWhile(_ < _)
res1: scala.collection.immutable.Vector[scala.collection.immutable.Vector[Int]] =
  Vector(Vector(1, 2, 3, 4), Vector(1, 2, 3), Vector(1, 2), Vector(1))

有用!

唯一的问题是，我们通常不会将这些方法用于数组，因为这将需要在一行中进行两次隐式转换。有几种方法可以解决此问题，包括为数组编写单独的隐式转换，转换为WrappedArray等等。

编辑:我最喜欢的处理数组和字符串的方法是使代码更加通用，然后使用适当的隐式转换使它们再次更具体，从而使数组也可以工作。在这种情况下:

class GroupingCollection[A, C, D[C]](ca: C)(
  implicit c2i: C => Iterable[A],
           cbf: CanBuildFrom[C,C,D[C]],
           cbfi: CanBuildFrom[C,A,C]
) {
  def groupedWhile(p: (A,A) => Boolean): D[C] = {
    val it = c2i(ca).iterator
    val cca = cbf()
    if (!it.hasNext) cca.result
    else {
      val as = cbfi()
      var olda = it.next
      as += olda
      while (it.hasNext) {
        val a = it.next
        if (p(olda,a)) as += a
        else { cca += as.result; as.clear; as += a }
        olda = a
      }
      cca += as.result
    }
    cca.result
  }
}

在这里我们添加了一个隐式函数，从Iterable[A]中给我们提供了一个C-对于大多数集合来说，这只是身份(例如List[A]已经是一个Iterable[A])，但是对于数组而言，它将是一个真正的隐式转换。而且，因此，我们放弃了C[A] <: Iterable[A]的要求-我们基本上只是将<%的要求明确化了，因此我们可以随意显式使用它，而不必让编译器为我们填充它。另外，我们放宽了对collection-of-collections的限制，即C[C[A]]，而不是任何D[C]，我们稍后将填写这些内容成为我们想要的。因为我们稍后将填写它，所以将其推到类级别而不是方法级别。否则，基本上是相同的。

现在的问题是如何使用它。对于常规收藏，我们可以:

implicit def collections_have_grouping[A, C[A]](ca: C[A])(
  implicit c2i: C[A] => Iterable[A],
           cbf: CanBuildFrom[C[A],C[A],C[C[A]]],
           cbfi: CanBuildFrom[C[A],A,C[A]]
) = {
  new GroupingCollection[A,C[A],C](ca)(c2i, cbf, cbfi)
}

现在，我们在C[A]中插入C，在C[C[A]]中插入D[C]。请注意，我们确实需要对new GroupingCollection的调用使用显式的泛型类型，以便它可以直接确定哪些类型对应什么。多亏了implicit c2i: C[A] => Iterable[A]，它可以自动处理数组。

但是等等，如果我们想使用字符串怎么办？现在我们遇到了麻烦，因为您不能拥有“字符串字符串”。这是额外的抽象帮助的地方:我们可以将D称为适合容纳字符串的名称。让我们选择Vector，然后执行以下操作:

val vector_string_builder = (
  new CanBuildFrom[String, String, Vector[String]] {
    def apply() = Vector.newBuilder[String]
    def apply(from: String) = this.apply()
  }
)

implicit def strings_have_grouping(s: String)(
  implicit c2i: String => Iterable[Char],
           cbfi: CanBuildFrom[String,Char,String]
) = {
  new GroupingCollection[Char,String,Vector](s)(
    c2i, vector_string_builder, cbfi
  )
}

我们需要一个新的CanBuildFrom来处理字符串 vector 的构建(但这确实很容易，因为我们只需要调用Vector.newBuilder[String]即可)，然后我们需要填写所有类型，以便合理地键入GroupingCollection。请注意，我们已经在[String,Char,String] CanBuildFrom周围 float 了，因此可以从char集合中创建字符串。

让我们尝试一下:

scala> List(true,false,true,true,true).groupedWhile(_ == _)
res1: List[List[Boolean]] = List(List(true), List(false), List(true, true, true))

scala> Array(1,2,5,3,5,6,7,4,1).groupedWhile(_ <= _) 
res2: Array[Array[Int]] = Array(Array(1, 2, 5), Array(3, 5, 6, 7), Array(4), Array(1))

scala> "Hello there!!".groupedWhile(_.isLetter == _.isLetter)
res3: Vector[String] = Vector(Hello,  , there, !!)