對一個集合進行抽象

Question

最近，我爲Anys的笛卡爾積寫了一個迭代器，並開始使用列表清單，但是認識到我可以輕鬆切換到更抽象的特質Seq。

我知道，你喜歡看代碼。 :)

class Cartesian (val ll: Seq[Seq[_]]) extends Iterator [Seq[_]] { 

    def combicount: Int = (1 /: ll) (_ * _.length) 

    val last = combicount 
    var iter = 0 

    override def hasNext(): Boolean = iter < last 
    override def next(): Seq[_] = { 
    val res = combination (ll, iter) 
    iter += 1 
    res 
    } 

    def combination (xx: Seq [Seq[_]], i: Int): List[_] = xx match { 
     case Nil  => Nil 
     case x :: xs => x (i % x.length) :: combination (xs, i/x.length) 
    } 
} 

而那類的客戶端：

object Main extends Application { 
    val illi = new Cartesian (List ("abc".toList, "xy".toList, "AB".toList)) 
    // val ivvi = new Cartesian (Vector (Vector (1, 2, 3), Vector (10, 20))) 
    val issi = new Cartesian (Seq (Seq (1, 2, 3), Seq (10, 20))) 
    // val iaai = new Cartesian (Array (Array (1, 2, 3), Array (10, 20))) 

    (0 to 5).foreach (dummy => println (illi.next())) 
    // (0 to 5).foreach (dummy => println (issi.next())) 
} 
/* 
List(a, x, A) 
List(b, x, A) 
List(c, x, A) 
List(a, y, A) 
List(b, y, A) 
List(c, y, A) 
*/ 

的代碼可以很好地用於序列和列表（這是Seqs），但當然不是數組或向量，這是不類型爲Seq，並且沒有cons ::'的方法。

但是邏輯也可以用於這樣的集合。

我可以嘗試爲Vector，Array等編寫一個隱式向Seq的轉換，或者嘗試編寫一個自己的類似實現，或者編寫一個Wrapper，將集合轉換爲Seq的Seq，然後爲內部集合調用'hasNext'和'next'，並將結果轉換爲Array，Vector或其他。 （我試圖實現這樣的解決方法，但我必須認識到：並不那麼容易，對於現實世界的問題，我可能會獨立地重寫Iterator。）

但是，如果我的整個事情變得有點失控必須處理列表陣列或陣列列表和其他混合案例。

以最廣泛，最可能的方式編寫算法最優雅的方式是什麼？

Answer 1

有兩種解決方案。首先是不要求容器是某個通用超類的子類，而是可以轉換爲一個（通過使用隱式函數參數）。如果容器已經是所需類型的子類，則只有一個預定義的標識轉換，它只返回它。

import collection.mutable.Builder 
import collection.TraversableLike 
import collection.generic.CanBuildFrom 
import collection.mutable.SeqLike 

class Cartesian[T, ST[T], TT[S]](val ll: TT[ST[T]])(implicit cbf: CanBuildFrom[Nothing, T, ST[T]], seqLike: ST[T] => SeqLike[T, ST[T]], traversableLike: TT[ST[T]] => TraversableLike[ST[T], TT[ST[T]]]) extends Iterator[ST[T]] { 

    def combicount(): Int = (1 /: ll) (_ * _.length) 

    val last = combicount - 1 
    var iter = 0 

    override def hasNext(): Boolean = iter < last 
    override def next(): ST[T] = { 
    val res = combination (ll, iter, cbf()) 
    iter += 1 
    res 
    } 

    def combination (xx: TT[ST[T]], i: Int, builder: Builder[T, ST[T]]): ST[T] = 
    if (xx.isEmpty) builder.result 
    else combination (xx.tail, i/xx.head.length, builder += xx.head (i % xx.head.length)) 
} 

這類作品：

scala> new Cartesian[String, Vector, Vector](Vector(Vector("a"), Vector("xy"), Vector("AB"))) 
res0: Cartesian[String,Vector,Vector] = empty iterator 

scala> new Cartesian[String, Array, Array](Array(Array("a"), Array("xy"), Array("AB"))) 
res1: Cartesian[String,Array,Array] = empty iterator 

我需要明確地傳遞，因爲錯誤https://issues.scala-lang.org/browse/SI-3343

有一點要注意的類型是，這是比使用存在類型比較好，因爲調用迭代器上的下一個返回正確的類型，而不是Seq [Any]。

有幾個缺點這裏：

• 如果容器不是所需的類型的子類，它被轉換爲一個，這在性能
• 成本的算法是不完全通用。我們需要將類型轉換爲SeqLike或TraversableLike，才能使用這些類型提供的功能子集。所以製作一個轉換函數可能會很棘手。
• 如果某些功能在不同的環境下可以有不同的解釋，該怎麼辦？例如，矩形具有兩個「長度」屬性（寬度和高度）

現在爲替代解決方案。我們注意到，我們並不真正關心的各類收藏品，只是他們的能力：

• TT應該有foldLeft，get(i: Int)（獲得頭/尾）
• ST應有length，get(i: Int)和生成器

所以我們可以編碼這些：

trait HasGet[T, CC[_]] { 
    def get(cc: CC[T], i: Int): T 
} 

object HasGet { 
    implicit def seqLikeHasGet[T, CC[X] <: SeqLike[X, _]] = new HasGet[T, CC] { 
    def get(cc: CC[T], i: Int): T = cc(i) 
    } 

    implicit def arrayHasGet[T] = new HasGet[T, Array] { 
    def get(cc: Array[T], i: Int): T = cc(i) 
    } 
} 

trait HasLength[CC] { 
    def length(cc: CC): Int 
} 

object HasLength { 
    implicit def seqLikeHasLength[CC <: SeqLike[_, _]] = new HasLength[CC] { 
    def length(cc: CC) = cc.length 
    } 

    implicit def arrayHasLength[T] = new HasLength[Array[T]] { 
    def length(cc: Array[T]) = cc.length 
    } 

} 

trait HasFold[T, CC[_]] { 
    def foldLeft[A](cc: CC[T], zero: A)(op: (A, T) => A): A 
} 

object HasFold { 
    implicit def seqLikeHasFold[T, CC[X] <: SeqLike[X, _]] = new HasFold[T, CC] { 
    def foldLeft[A](cc: CC[T], zero: A)(op: (A, T) => A): A = cc.foldLeft(zero)(op) 
    } 
    implicit def arrayHasFold[T] = new HasFold[T, Array] { 
    def foldLeft[A](cc: Array[T], zero: A)(op: (A, T) => A): A = { 
     var i = 0 
     var result = zero 
     while (i < cc.length) { 
     result = op(result, cc(i)) 
     i += 1 
     } 
     result 
    } 
    } 
} 

（嚴格地說，HasFold不requi自實施以來，紅色是在長度方面和得到的，但我在這裏補充它，因此算法將轉化更乾淨）

現在的算法是：

class Cartesian[T, ST[_], TT[Y]](val ll: TT[ST[T]])(implicit cbf: CanBuildFrom[Nothing, T, ST[T]], stHasLength: HasLength[ST[T]], stHasGet: HasGet[T, ST], ttHasFold: HasFold[ST[T], TT], ttHasGet: HasGet[ST[T], TT], ttHasLength: HasLength[TT[ST[T]]]) extends Iterator[ST[T]] { 

    def combicount(): Int = ttHasFold.foldLeft(ll, 1)((a,l) => a * stHasLength.length(l)) 

    val last = combicount - 1 
    var iter = 0 

    override def hasNext(): Boolean = iter < last 
    override def next(): ST[T] = { 
    val res = combination (ll, 0, iter, cbf()) 
    iter += 1 
    res 
    } 

    def combination (xx: TT[ST[T]], j: Int, i: Int, builder: Builder[T, ST[T]]): ST[T] = 
    if (ttHasLength.length(xx) == j) builder.result 
    else { 
     val head = ttHasGet.get(xx, j) 
     val headLength = stHasLength.length(head) 
     combination (xx, j + 1, i/headLength, builder += stHasGet.get(head, (i % headLength))) 
    } 
} 

及用途：

scala> new Cartesian[String, Vector, List](List(Vector("a"), Vector("xy"), Vector("AB"))) 
res6: Cartesian[String,Vector,List] = empty iterator 

scala> new Cartesian[String, Array, Array](Array(Array("a"), Array("xy"), Array("AB"))) 
res7: Cartesian[String,Array,Array] = empty iterator 

斯卡拉斯可能已經爲你預定了所有這些，不幸的是，我不太清楚它。

（我再次需要通過類型，因爲推論並不推斷正確的）

的好處是，該算法現在完全通用的，沒有必要從Array到WrappedArray在隱式轉換爲了它的工作

鍛鍊; Tibial：定義的元組;-)