具有泛型类型的泛型集合生成

吉拉德高

有时,我发现自己希望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事件与ListSeq等” ...

所以我尝试了另一种方法:

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)非常热切,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将其移动到另一个对象或类,则用户根本不必导入任何与之相关的东西Unfolder3

如果您不了解此实现的工作方式,则可以阅读有关Scala中的typeclass模式隐式解析顺序的信息

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

具有泛型类型的泛型集合生成

来自分类Dev

泛型类型集合

来自分类Dev

特定枚举类型的“集合”,但具有泛型

来自分类Dev

具有泛型的Java排序集合

来自分类Dev

具有参数化集合的泛型?

来自分类Dev

具有多个特征的泛型类型

来自分类Dev

创建具有泛型类型的函数

来自分类Dev

具有泛型的Scala类型类

来自分类Dev

具有多个泛型类型的ArrayList?

来自分类Dev

具有接口类类型的泛型

来自分类Dev

具有泛型类型的contains()

来自分类Dev

具有泛型类型的属性

来自分类Dev

如何为泛型类指定泛型集合类型?

来自分类Dev

Java泛型-具有“扩展”类型的集合参数的方法拒绝有效的参数?

来自分类Dev

调用具有多个泛型类型的泛型方法,而无需指定每个泛型类型

来自分类Dev

在集合中存储具有不同泛型类型参数的项目

来自分类Dev

类中具有2个泛型类型的方法,其中1个泛型类型

来自分类Dev

类中具有2个泛型类型的方法,其中1个泛型类型

来自分类Dev

具有继承的泛型

来自分类Dev

具有多个类型参数的泛型推断类型

来自分类Dev

使泛型类的函数仅接受具有相同泛型类型但受更多约束的参数

来自分类Dev

在C#中检查T泛型类型具有属性S(泛型)

来自分类Dev

具有不同类型泛型参数的方法的泛型类

来自分类Dev

具有非泛型类型 T 的子代的泛型<T> ActionResult

来自分类Dev

如何使用已知类型作为参数创建具有泛型的泛型类?

来自分类Dev

C#集合类型约束泛型

来自分类Dev

泛型类型,集合和对象引用

来自分类Dev

集合对泛型类型进行排序Java

来自分类Dev

投射泛型集合项类型

Related 相关文章

热门标签

归档