对一个集合进行抽象

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：定义的元组;-)