泛型集合的生成與一般類型

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。