scala - 如何将丰富我的库模式应用于 Scala 集合？

Question

Scala 中最强大的模式之一是丰富我的库* 模式，它使用隐式转换来向现有类添加方法，而无需动态方法解析。例如，如果我们希望所有字符串都具有方法 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]] ?

* 以前称为 pimp-my-library。

Answer 1

理解这个问题的关键是要意识到有两种不同的方式来构建和使用集合库中的集合。一个是公共(public)集合接口(interface)及其所有好的方法。另一个广泛用于创建集合库，但几乎从未在它之外使用过的，是构建器。

我们丰富的问题​​与集合库本身在尝试返回相同类型的集合时面临的问题完全相同。也就是说，我们想要构建集合，但是在一般工作时，我们没有办法引用“与集合已经是相同的类型”。所以我们需要 build 者。

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

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

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

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

我们从隐式 CanBuildFrom 中获得这些构建器s，不是直接来自我们的收藏。

让我们看一个例子。

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 s 和构建 C[A] s，还有一个需要 C[A] s 和构建 C[C[A]] s。查看 CanBuildFrom 的类型签名，我们看到

CanBuildFrom[-From, -Elem, +To]

这意味着 CanBuildFrom 想知道我们开始使用的集合类型——在我们的例子中，它是 C[A] ，然后是生成的集合的元素和该集合的类型。所以我们将它们填入隐式参数 cbfcc和 cbfc .

意识到这一点后，这就是大部分工作。我们可以使用我们的 CanBuildFrom s 为我们提供构建器(您需要做的就是应用它们)。一个 build 者可以建立一个集合 += ，将其转换为最终应该与 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] 的要求。 --我们基本上只是对<%提出了要求显式，所以我们可以随意显式地使用它，而不是让编译器为我们填写它。此外，我们放宽了我们的收藏集为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.newBuilder[String] )，然后我们需要填写所有类型，以便 GroupingCollection是明智地键入。请注意，我们已经在 [String,Char,String] 周围 float 了CanBuildFrom，所以字符串可以由字符集合组成。

让我们试试看:

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, !!)