有时,我发现自己希望scala集合包含一些缺少的功能,并且很容易“扩展”集合并提供自定义方法。
从头开始构建集合时,这会有些困难。考虑有用的方法,例如.iterate
。我将使用类似的熟悉功能演示用例:unfold
。
unfold
是一种从初始状态构造集合的方法z: S
,以及一种用于生成下一个状态的可选元组的函数以及一个elementE
或指示结束的空选项的函数。
对于某些集合类型,方法签名Coll[T]
应大致如下:
def unfold[S,E](z: S)(f: S ⇒ Option[(S,E)]): Coll[E]
现在,IMO,最“自然”的用法应该是:
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()
}
}
在范围内使用此隐式类,我们可以为Fibonacci seq生成一个数组,如下所示:
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
}
但这也不是正确的。我不喜欢强迫用户导入某些东西,更不用说隐式方法了,该方法将在每个方法调用上创建一个无用的接线类。而且,没有简单的方法可以覆盖默认逻辑。您可以考虑诸如之类的集合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
不是唯一要全局添加的功能,那么覆盖默认实现仍然很困难。底线,这很难维护,也不会“感觉”正确。
那么,有没有更好的方法来实现这一目标?
首先,让我们对该函数进行基本实现,它使用一个显式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)
}
}
现在,按类型获取集合构建器的简单方法是什么?
我可以提出两个可能的解决方案。首先是创建一个隐式扩展类,该类扩展了GenericCompanion
–大多数scala内置集合的通用超类。该GenericCompanion
方法具有一个针对提供的元素类型newBuilder
返回的方法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
或用户定义的集合。
另一个可能的解决方案是使用隐式的“构建器提供程序”,如您所建议的。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
使用a Builder
,对于aStream
来说它是eager。
要懒散Stream
地进行展开,您不能使用standard 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
)非常热切,对Stream
s则是惰性的:
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
将其移动到另一个对象或类,则用户根本不必导入任何与之相关的东西Unfolder3
。
如果您不了解此实现的工作方式,则可以阅读有关Scala中的typeclass模式和隐式解析顺序的信息。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句