泛型集合的生成与一般类型

Question

有时，我发现自己希望scala集合包含一些缺失的功能，并且它很容易“扩展”集合，并提供自定义方法。

这对于从头开始构建集合有点困难。 考虑有用的方法，如.iterate。 我将用类似的熟悉函数演示用例：unfold。

unfold是构造从初始状态z: S集合，以产生下一个状态的一个可选的元组的功能，并且一个元件E，或者指示结束的空选项的方法。

方法签名，对于一些集合类型Coll[T]应该大致如下：

def unfold[S,E](z: S)(f: S ⇒ Option[(S,E)]): Coll[E] 

现在，国际海事组织，最 “自然” 的用法应该是，例如：

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() 
    } 
} 

with t他在范围内隐类，我们可以生成斐波那契序列是这样一个数组：

val arr: Array[Int] = Array.unfold(0->1) { 
    case (a,b) if a < 256 => Some((b -> (a+b)) -> a) 
    case _    => None 
} 

但是，如果我们要提供这个功能给所有其他集合类型，我看比到C & P中的任何其他选择代码，并与List，Seq替换所有Array出现，等等” ......

所以，我想另一种方法：

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不是全局添加的唯一函数，并且覆盖默认实现仍然很困难。底线，这很难维持，也不“感觉”正确。

那么，有没有更好的方法来实现这一目标？

Answer 1

首先，我们来做一个基本的函数实现，它使用一个明确的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 s。这主要是因为原始实施UnfoldImpl.unfold使用Builder，其对于Stream是eager。

要做一些类似懒惰的展开Stream，您不能使用标准Builder。您必须使用Stream.cons（或#::）提供单独的实施。为了能够自动选择实现，取决于用户请求的集合类型，可以使用类型类型模式。下面是一个简单的实现：

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 patern和order of implicit resolution。