具有通用类型的通用集合生成
generic collection generation with a generic type
有时，我发现自己希望 scala 集合包含一些缺少的功能，"extending" 集合并提供自定义方法相当容易。
从头开始构建集合时，这有点困难。
考虑有用的方法，例如 .iterate。
我将用类似的、熟悉的函数来演示用例：unfold.
unfold是一种从初始状态z: S构造集合的方法，以及生成下一个状态的可选元组的函数，以及一个元素E，或者表示结束的空选项。
方法签名，对于某些集合类型 Coll[T] 应该大致如下：
def unfold[S,E](z: S)(f: S ⇒ Option[(S,E)]): Coll[E]
现在，IMO，最 "natural" 用法应该是，例如：
val state: S = ??? // initial state
val arr: Array[E] = Array.unfold(state){ s ⇒
// code to convert s to some Option[(S,E)]
???
}
对于特定的集合类型，这非常简单：
implicit class ArrayOps(arrObj: Array.type) {
def unfold[S,E : ClassTag](z: S)(f: S => Option[(S,E)]): Array[E] = {
val b = Array.newBuilder[E]
var s = f(z)
while(s.isDefined) {
val Some((state,element)) = s
b += element
s = f(state)
}
b.result()
}
}
在范围内使用这个隐式 class，我们可以像这样为斐波那契数列生成一个数组：
val arr: Array[Int] = Array.unfold(0->1) {
case (a,b) if a < 256 => Some((b -> (a+b)) -> a)
case _ => None
}
但是如果我们想为所有其他集合类型提供此功能，我认为除了 C&P 代码之外别无选择，并将所有 Array 替换为 List、Seq,等等'...
所以我尝试了另一种方法：
trait BuilderProvider[Elem,Coll] {
def builder: mutable.Builder[Elem,Coll]
}
object BuilderProvider {
object Implicits {
implicit def arrayBuilderProvider[Elem : ClassTag] = new BuilderProvider[Elem,Array[Elem]] {
def builder = Array.newBuilder[Elem]
}
implicit def listBuilderProvider[Elem : ClassTag] = new BuilderProvider[Elem,List[Elem]] {
def builder = List.newBuilder[Elem]
}
// many more logicless implicits
}
}
def unfold[Coll,S,E : ClassTag](z: S)(f: S => Option[(S,E)])(implicit bp: BuilderProvider[E,Coll]): Coll = {
val b = bp.builder
var s = f(z)
while(s.isDefined) {
val Some((state,element)) = s
b += element
s = f(state)
}
b.result()
}
现在，在上述范围内，所有需要的是正确类型的导入：
import BuilderProvider.Implicits.arrayBuilderProvider
val arr: Array[Int] = unfold(0->1) {
case (a,b) if a < 256 => Some((b -> (a+b)) -> a)
case _ => None
}
但这也不对。我不喜欢强迫用户导入某些东西，更不用说在每次方法调用时都会创建无用连接 class 的隐式方法了。此外，没有简单的方法来覆盖默认逻辑。您可以考虑诸如 Stream 之类的集合，其中最适合延迟创建集合，或者考虑其他集合的其他特殊实现细节。
我能想到的最佳解决方案是使用第一个解决方案作为模板，并使用 sbt 生成源代码：
sourceGenerators in Compile += Def.task {
val file = (sourceManaged in Compile).value / "myextensions" / "util" / "collections" / "package.scala"
val colls = Seq("Array","List","Seq","Vector","Set") //etc'...
val prefix = s"""package myextensions.util
|
|package object collections {
|
""".stripMargin
val all = colls.map{ coll =>
s"""
|implicit class ${coll}Ops[Elem](obj: ${coll}.type) {
| def unfold[S,E : ClassTag](z: S)(f: S => Option[(S,E)]): ${coll}[E] = {
| val b = ${coll}.newBuilder[E]
| var s = f(z)
| while(s.isDefined) {
| val Some((state,element)) = s
| b += element
| s = f(state)
| }
| b.result()
| }
|}
""".stripMargin
}
IO.write(file,all.mkString(prefix,"\n","\n}\n"))
Seq(file)
}.taskValue
但此解决方案存在其他问题，并且难以维护。试想一下，如果 unfold 不是唯一要全局添加的函数，那么覆盖默认实现仍然很困难。最重要的是，这很难维护，也不 "feel" 正确。
那么，有没有更好的方法来实现这一点？
首先，让我们做一个函数的基本实现，它使用显式 Builder 参数。在展开的情况下，它看起来像这样：
import scala.language.higherKinds
import scala.annotation.tailrec
import scala.collection.GenTraversable
import scala.collection.mutable
import scala.collection.generic.{GenericCompanion, CanBuildFrom}
object UnfoldImpl {
def unfold[CC[_], E, S](builder: mutable.Builder[E, CC[E]])(initial: S)(next: S => Option[(S, E)]): CC[E] = {
@tailrec
def build(state: S): CC[E] = {
next(state) match {
case None => builder.result()
case Some((nextState, elem)) =>
builder += elem
build(nextState)
}
}
build(initial)
}
}
现在，什么是按类型获取集合构建器的简单方法？
我可以提出两个可能的解决方案。第一个是做一个隐式扩展 class，它扩展了一个 GenericCompanion——大多数 scala 内置集合的公共 superclass。此 GenericCompanion 有一个方法 newBuilder，returns 一个 Builder 用于提供的元素类型。实现可能如下所示：
implicit class Unfolder[CC[X] <: GenTraversable[X]](obj: GenericCompanion[CC]) {
def unfold[S, E](initial: S)(next: S => Option[(S, E)]): CC[E] =
UnfoldImpl.unfold(obj.newBuilder[E])(initial)(next)
}
使用起来非常简单：
scala> List.unfold(1)(a => if (a > 10) None else Some(a + 1, a * a))
res1: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
一个缺点是某些集合没有扩展 GenericCompanion 的伴生对象。例如，Array，或用户定义的集合。
另一种可能的解决方案是使用隐式 'builder provider'，就像您所建议的那样。而scala的集合库中已经有了这样的东西。是 CanBuildFrom。 CanBuildFrom 的实现可能如下所示：
object Unfolder2 {
def apply[CC[_]] = new {
def unfold[S, E](initial: S)(next: S => Option[(S, E)])(
implicit cbf: CanBuildFrom[CC[E], E, CC[E]]
): CC[E] =
UnfoldImpl.unfold(cbf())(initial)(next)
}
}
用法示例：
scala> Unfolder2[Array].unfold(1)(a => if (a > 10) None else Some(a + 1, a * a))
res1: Array[Int] = Array(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
这适用于 scala 的集合，Array，并且如果用户提供了 CanBuildFrom 实例，则可能适用于用户定义的集合。
请注意，这两种方法都不适用于 Stream 以惰性方式。这主要是因为原始实现 UnfoldImpl.unfold 使用了 Builder，对于 Stream 是 eager.
懒惰地为 Stream 做一些类似展开的事情，你不能使用标准的 Builder。您必须使用 Stream.cons（或 #::）提供单独的实现。为了能够根据用户请求的集合类型自动选择实现，您可以使用 typeclass 模式。这是一个示例实现：
trait Unfolder3[E, CC[_]] {
def unfold[S](initial: S)(next: S => Option[(S, E)]): CC[E]
}
trait UnfolderCbfInstance {
// provides unfolder for types that have a `CanBuildFrom`
// this is used only if the collection is not a `Stream`
implicit def unfolderWithCBF[E, CC[_]](
implicit cbf: CanBuildFrom[CC[E], E, CC[E]]
): Unfolder3[E, CC] =
new Unfolder3[E, CC] {
def unfold[S](initial: S)(next: S => Option[(S, E)]): CC[E] =
UnfoldImpl.unfold(cbf())(initial)(next)
}
}
object Unfolder3 extends UnfolderCbfInstance {
// lazy implementation, that overrides `unfolderWithCbf` for `Stream`s
implicit def streamUnfolder[E]: Unfolder3[E, Stream] =
new Unfolder3[E, Stream] {
def unfold[S](initial: S)(next: S => Option[(S, E)]): Stream[E] =
next(initial).fold(Stream.empty[E]) {
case (state, elem) =>
elem #:: unfold(state)(next)
}
}
def apply[CC[_]] = new {
def unfold[E, S](initial: S)(next: S => Option[(S, E)])(
implicit impl: Unfolder3[E, CC]
): CC[E] = impl.unfold(initial)(next)
}
}
现在这个实现对普通集合（包括 Array 和具有适当 CanBuildFrom 的用户定义集合）非常有效，对 Streams:
是惰性的
scala> Unfolder3[Array].unfold(1)(a => if (a > 10) None else Some(a + 1, a * a))
res0: Array[Int] = Array(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
scala> com.Main.Unfolder3[Stream].unfold(1)(a => if (a > 10) None else { println(a); Some(a + 1, a * a) })
1
res2: Stream[Int] = Stream(1, ?)
scala> res2.take(3).toList
2
3
res3: List[Int] = List(1, 4, 9)
请注意，如果 Unfolder3.apply 被移动到另一个对象或 class，用户根本不需要导入任何与 Unfolder3 有关的内容。
如果您不了解此实现的工作原理，您可以阅读有关 typeclass patern in Scala, and the order of implicit resolution.
的内容
有时，我发现自己希望 scala 集合包含一些缺少的功能，"extending" 集合并提供自定义方法相当容易。
从头开始构建集合时，这有点困难。
考虑有用的方法，例如 .iterate。
我将用类似的、熟悉的函数来演示用例：unfold.
unfold是一种从初始状态z: S构造集合的方法，以及生成下一个状态的可选元组的函数，以及一个元素E，或者表示结束的空选项。
方法签名，对于某些集合类型 Coll[T] 应该大致如下：
def unfold[S,E](z: S)(f: S ⇒ Option[(S,E)]): Coll[E]
现在，IMO，最 "natural" 用法应该是，例如：
val state: S = ??? // initial state
val arr: Array[E] = Array.unfold(state){ s ⇒
// code to convert s to some Option[(S,E)]
???
}
对于特定的集合类型，这非常简单：
implicit class ArrayOps(arrObj: Array.type) {
def unfold[S,E : ClassTag](z: S)(f: S => Option[(S,E)]): Array[E] = {
val b = Array.newBuilder[E]
var s = f(z)
while(s.isDefined) {
val Some((state,element)) = s
b += element
s = f(state)
}
b.result()
}
}
在范围内使用这个隐式 class，我们可以像这样为斐波那契数列生成一个数组：
val arr: Array[Int] = Array.unfold(0->1) {
case (a,b) if a < 256 => Some((b -> (a+b)) -> a)
case _ => None
}
但是如果我们想为所有其他集合类型提供此功能，我认为除了 C&P 代码之外别无选择，并将所有 Array 替换为 List、Seq,等等'...
所以我尝试了另一种方法：
trait BuilderProvider[Elem,Coll] {
def builder: mutable.Builder[Elem,Coll]
}
object BuilderProvider {
object Implicits {
implicit def arrayBuilderProvider[Elem : ClassTag] = new BuilderProvider[Elem,Array[Elem]] {
def builder = Array.newBuilder[Elem]
}
implicit def listBuilderProvider[Elem : ClassTag] = new BuilderProvider[Elem,List[Elem]] {
def builder = List.newBuilder[Elem]
}
// many more logicless implicits
}
}
def unfold[Coll,S,E : ClassTag](z: S)(f: S => Option[(S,E)])(implicit bp: BuilderProvider[E,Coll]): Coll = {
val b = bp.builder
var s = f(z)
while(s.isDefined) {
val Some((state,element)) = s
b += element
s = f(state)
}
b.result()
}
现在，在上述范围内，所有需要的是正确类型的导入：
import BuilderProvider.Implicits.arrayBuilderProvider
val arr: Array[Int] = unfold(0->1) {
case (a,b) if a < 256 => Some((b -> (a+b)) -> a)
case _ => None
}
但这也不对。我不喜欢强迫用户导入某些东西，更不用说在每次方法调用时都会创建无用连接 class 的隐式方法了。此外，没有简单的方法来覆盖默认逻辑。您可以考虑诸如 Stream 之类的集合，其中最适合延迟创建集合，或者考虑其他集合的其他特殊实现细节。
我能想到的最佳解决方案是使用第一个解决方案作为模板，并使用 sbt 生成源代码：
sourceGenerators in Compile += Def.task {
val file = (sourceManaged in Compile).value / "myextensions" / "util" / "collections" / "package.scala"
val colls = Seq("Array","List","Seq","Vector","Set") //etc'...
val prefix = s"""package myextensions.util
|
|package object collections {
|
""".stripMargin
val all = colls.map{ coll =>
s"""
|implicit class ${coll}Ops[Elem](obj: ${coll}.type) {
| def unfold[S,E : ClassTag](z: S)(f: S => Option[(S,E)]): ${coll}[E] = {
| val b = ${coll}.newBuilder[E]
| var s = f(z)
| while(s.isDefined) {
| val Some((state,element)) = s
| b += element
| s = f(state)
| }
| b.result()
| }
|}
""".stripMargin
}
IO.write(file,all.mkString(prefix,"\n","\n}\n"))
Seq(file)
}.taskValue
但此解决方案存在其他问题，并且难以维护。试想一下，如果 unfold 不是唯一要全局添加的函数，那么覆盖默认实现仍然很困难。最重要的是，这很难维护，也不 "feel" 正确。
那么，有没有更好的方法来实现这一点？
首先，让我们做一个函数的基本实现，它使用显式 Builder 参数。在展开的情况下，它看起来像这样：
import scala.language.higherKinds
import scala.annotation.tailrec
import scala.collection.GenTraversable
import scala.collection.mutable
import scala.collection.generic.{GenericCompanion, CanBuildFrom}
object UnfoldImpl {
def unfold[CC[_], E, S](builder: mutable.Builder[E, CC[E]])(initial: S)(next: S => Option[(S, E)]): CC[E] = {
@tailrec
def build(state: S): CC[E] = {
next(state) match {
case None => builder.result()
case Some((nextState, elem)) =>
builder += elem
build(nextState)
}
}
build(initial)
}
}
现在，什么是按类型获取集合构建器的简单方法？
我可以提出两个可能的解决方案。第一个是做一个隐式扩展 class，它扩展了一个 GenericCompanion——大多数 scala 内置集合的公共 superclass。此 GenericCompanion 有一个方法 newBuilder，returns 一个 Builder 用于提供的元素类型。实现可能如下所示：
implicit class Unfolder[CC[X] <: GenTraversable[X]](obj: GenericCompanion[CC]) {
def unfold[S, E](initial: S)(next: S => Option[(S, E)]): CC[E] =
UnfoldImpl.unfold(obj.newBuilder[E])(initial)(next)
}
使用起来非常简单：
scala> List.unfold(1)(a => if (a > 10) None else Some(a + 1, a * a))
res1: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
一个缺点是某些集合没有扩展 GenericCompanion 的伴生对象。例如，Array，或用户定义的集合。
另一种可能的解决方案是使用隐式 'builder provider'，就像您所建议的那样。而scala的集合库中已经有了这样的东西。是 CanBuildFrom。 CanBuildFrom 的实现可能如下所示：
object Unfolder2 {
def apply[CC[_]] = new {
def unfold[S, E](initial: S)(next: S => Option[(S, E)])(
implicit cbf: CanBuildFrom[CC[E], E, CC[E]]
): CC[E] =
UnfoldImpl.unfold(cbf())(initial)(next)
}
}
用法示例：
scala> Unfolder2[Array].unfold(1)(a => if (a > 10) None else Some(a + 1, a * a))
res1: Array[Int] = Array(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
这适用于 scala 的集合，Array，并且如果用户提供了 CanBuildFrom 实例，则可能适用于用户定义的集合。
请注意，这两种方法都不适用于 Stream 以惰性方式。这主要是因为原始实现 UnfoldImpl.unfold 使用了 Builder，对于 Stream 是 eager.
懒惰地为 Stream 做一些类似展开的事情，你不能使用标准的 Builder。您必须使用 Stream.cons（或 #::）提供单独的实现。为了能够根据用户请求的集合类型自动选择实现，您可以使用 typeclass 模式。这是一个示例实现：
trait Unfolder3[E, CC[_]] {
def unfold[S](initial: S)(next: S => Option[(S, E)]): CC[E]
}
trait UnfolderCbfInstance {
// provides unfolder for types that have a `CanBuildFrom`
// this is used only if the collection is not a `Stream`
implicit def unfolderWithCBF[E, CC[_]](
implicit cbf: CanBuildFrom[CC[E], E, CC[E]]
): Unfolder3[E, CC] =
new Unfolder3[E, CC] {
def unfold[S](initial: S)(next: S => Option[(S, E)]): CC[E] =
UnfoldImpl.unfold(cbf())(initial)(next)
}
}
object Unfolder3 extends UnfolderCbfInstance {
// lazy implementation, that overrides `unfolderWithCbf` for `Stream`s
implicit def streamUnfolder[E]: Unfolder3[E, Stream] =
new Unfolder3[E, Stream] {
def unfold[S](initial: S)(next: S => Option[(S, E)]): Stream[E] =
next(initial).fold(Stream.empty[E]) {
case (state, elem) =>
elem #:: unfold(state)(next)
}
}
def apply[CC[_]] = new {
def unfold[E, S](initial: S)(next: S => Option[(S, E)])(
implicit impl: Unfolder3[E, CC]
): CC[E] = impl.unfold(initial)(next)
}
}
现在这个实现对普通集合（包括 Array 和具有适当 CanBuildFrom 的用户定义集合）非常有效，对 Streams:
scala> Unfolder3[Array].unfold(1)(a => if (a > 10) None else Some(a + 1, a * a))
res0: Array[Int] = Array(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
scala> com.Main.Unfolder3[Stream].unfold(1)(a => if (a > 10) None else { println(a); Some(a + 1, a * a) })
1
res2: Stream[Int] = Stream(1, ?)
scala> res2.take(3).toList
2
3
res3: List[Int] = List(1, 4, 9)
请注意，如果 Unfolder3.apply 被移动到另一个对象或 class，用户根本不需要导入任何与 Unfolder3 有关的内容。
如果您不了解此实现的工作原理，您可以阅读有关 typeclass patern in Scala, and the order of implicit resolution.
的内容