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

StackOverflow https://stackoverflow.com/questions/5410846

题

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

不幸的是，这种模式在处理泛型集合时会遇到麻烦。例如，有人问了很多问题 使用集合按顺序对项目进行分组. 。没有任何内置功能可以一次性完成，因此这似乎是使用通用集合来丰富我的库模式的理想候选者 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]]?

* 以前称为“皮条客我的图书馆”。

有帮助吗？

解决方案

理解这个问题的关键是要认识到有 构建和使用集合的两种不同方式 在馆藏图书馆里。第一个是公共集合接口及其所有好的方法。另一种广泛用于 创造 集合库是构建者，但几乎从不在它之外使用。

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

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

相反，我们的构建者来自 CanBuildFrom 浮动的隐式。这些专门用于匹配输入和输出类型并为您提供适当类型的构建器。

因此，我们需要实现两个概念上的飞跃：

  1. 我们不使用标准集合操作，我们使用构建器。
  2. 我们从隐式中获取这些构建器 CanBuildFroms，不是直接来自我们的收藏。

让我们看一个例子。

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]] 将所有团体聚集在一起。因此，我们需要两个构建器，其中一个需要 As 和构建 C[A]s，以及一个需要 C[A]s 和构建 C[C[A]]s。查看类型签名 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]--我们基本上刚刚提出了要求 <% 显式的，所以我们可以随意显式地使用它，而不是让编译器为我们填充它。此外，我们还放宽了收藏的限制 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 是明智地打字的。请注意，我们已经围绕 a 浮动了 [String,Char,String] 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, !!)

其他提示

作为 这次提交 与 Rex 给出出色答案时相比，“丰富”Scala 集合要容易得多。对于简单的情况，它可能看起来像这样，

import scala.collection.generic.{ CanBuildFrom, FromRepr, HasElem }
import language.implicitConversions

class FilterMapImpl[A, Repr](val r : Repr)(implicit hasElem : HasElem[Repr, A]) {
  def filterMap[B, That](f : A => Option[B])
    (implicit cbf : CanBuildFrom[Repr, B, That]) : That = r.flatMap(f(_).toSeq)
}

implicit def filterMap[Repr : FromRepr](r : Repr) = new FilterMapImpl(r)

这增加了“相同的结果类型”尊重 filterMap 对所有人进行操作 GenTraversableLikes,

scala> val l = List(1, 2, 3, 4, 5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> l.filterMap(i => if(i % 2 == 0) Some(i) else None)
res0: List[Int] = List(2, 4)

scala> val a = Array(1, 2, 3, 4, 5)
a: Array[Int] = Array(1, 2, 3, 4, 5)

scala> a.filterMap(i => if(i % 2 == 0) Some(i) else None)
res1: Array[Int] = Array(2, 4)

scala> val s = "Hello World"
s: String = Hello World

scala> s.filterMap(c => if(c >= 'A' && c <= 'Z') Some(c) else None)
res2: String = HW

对于问题中的示例，解决方案现在看起来像：

class GroupIdenticalImpl[A, Repr : FromRepr](val r: Repr)
  (implicit hasElem : HasElem[Repr, A]) {
  def groupIdentical[That](implicit cbf: CanBuildFrom[Repr,Repr,That]): That = {
    val builder = cbf(r)
    def group(r: Repr) : Unit = {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if(!rest.isEmpty)
        group(rest)
    }
    if(!r.isEmpty) group(r)
    builder.result
  }
}

implicit def groupIdentical[Repr : FromRepr](r: Repr) = new GroupIdenticalImpl(r)

REPL 会话示例，

scala> val l = List(1, 1, 2, 2, 3, 3, 1, 1)
l: List[Int] = List(1, 1, 2, 2, 3, 3, 1, 1)

scala> l.groupIdentical
res0: List[List[Int]] = List(List(1, 1),List(2, 2),List(3, 3),List(1, 1))

scala> val a = Array(1, 1, 2, 2, 3, 3, 1, 1)
a: Array[Int] = Array(1, 1, 2, 2, 3, 3, 1, 1)

scala> a.groupIdentical
res1: Array[Array[Int]] = Array(Array(1, 1),Array(2, 2),Array(3, 3),Array(1, 1))

scala> val s = "11223311"
s: String = 11223311

scala> s.groupIdentical
res2: scala.collection.immutable.IndexedSeq[String] = Vector(11, 22, 33, 11)

再次注意，相同的结果类型原则已经以完全相同的方式被观察到。 groupIdentical 直接定义于 GenTraversableLike.

作为 这次提交 与迈尔斯给出出色答案时相比，魔法咒语略有变化。

以下内容有效，但它是规范的吗？我希望其中一位经典能够纠正它。（或者更确切地说，大炮，大炮之一。）如果视图边界是上限，那么您将失去对数组和字符串的应用。边界是 GenTraversableLike 还是 TraversableLike 似乎并不重要；但 IsTraversableLike 为您提供 GenTraversableLike。

import language.implicitConversions
import scala.collection.{ GenTraversable=>GT, GenTraversableLike=>GTL, TraversableLike=>TL }
import scala.collection.generic.{ CanBuildFrom=>CBF, IsTraversableLike=>ITL }

class GroupIdenticalImpl[A, R <% GTL[_,R]](val r: GTL[A,R]) {
  def groupIdentical[That](implicit cbf: CBF[R, R, That]): That = {
    val builder = cbf(r.repr)
    def group(r: GTL[_,R]) {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if (!rest.isEmpty) group(rest)
    }
    if (!r.isEmpty) group(r)
    builder.result
  }
}

implicit def groupIdentical[A, R <% GTL[_,R]](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] =
  new GroupIdenticalImpl(fr conversion r)

用九条命剥猫皮的方法不止一种。这个版本说，一旦我的源转换为 GenTraversableLike，只要我可以从 GenTraversable 构建结果，就可以这样做。我对我的旧代表不感兴趣。

class GroupIdenticalImpl[A, R](val r: GTL[A,R]) {
  def groupIdentical[That](implicit cbf: CBF[GT[A], GT[A], That]): That = {
    val builder = cbf(r.toTraversable)
    def group(r: GT[A]) {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if (!rest.isEmpty) group(rest)
    }
    if (!r.isEmpty) group(r.toTraversable)
    builder.result
  }
}

implicit def groupIdentical[A, R](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] =
  new GroupIdenticalImpl(fr conversion r)

第一次尝试包括将 Repr 丑陋地转换为 GenTraversableLike。

import language.implicitConversions
import scala.collection.{ GenTraversableLike }
import scala.collection.generic.{ CanBuildFrom, IsTraversableLike }

type GT[A, B] = GenTraversableLike[A, B]
type CBF[A, B, C] = CanBuildFrom[A, B, C]
type ITL[A] = IsTraversableLike[A]

class FilterMapImpl[A, Repr](val r: GenTraversableLike[A, Repr]) { 
  def filterMap[B, That](f: A => Option[B])(implicit cbf : CanBuildFrom[Repr, B, That]): That = 
    r.flatMap(f(_).toSeq)
} 

implicit def filterMap[A, Repr](r: Repr)(implicit fr: ITL[Repr]): FilterMapImpl[fr.A, Repr] = 
  new FilterMapImpl(fr conversion r)

class GroupIdenticalImpl[A, R](val r: GT[A,R])(implicit fr: ITL[R]) { 
  def groupIdentical[That](implicit cbf: CBF[R, R, That]): That = { 
    val builder = cbf(r.repr)
    def group(r0: R) { 
      val r = fr conversion r0
      val first = r.head
      val (same, other) = r.span(_ == first)
      builder += same
      val rest = fr conversion other
      if (!rest.isEmpty) group(rest.repr)
    } 
    if (!r.isEmpty) group(r.repr)
    builder.result
  } 
} 

implicit def groupIdentical[A, R](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] = 
  new GroupIdenticalImpl(fr conversion r)
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top