对集合进行抽象

Question

最近，我为 Anys 的笛卡尔积编写了一个迭代器，并从 List of List 开始，但我认识到，我可以轻松切换到更抽象的特征 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)
*/

该代码适用于 Seq 和列表（它们是 Seq），但当然不适用于数组或向量，它们不是 Seq 类型，并且没有 cons-method ' ::'。

但这个逻辑也可以用于此类集合。

我可以尝试为 Vector、Array 等编写与 Seq 之间的隐式转换，或者尝试编写自己的类似实现，或者编写一个 Wrapper，它将集合转换为 Seq of Seq，并调用“hasNext” 'next' 表示内部集合，并将结果转换为数组、向量或其他类型。 （我试图实现这样的解决方法，但我必须认识到：这并不那么容易。对于现实世界的问题，我可能会独立重写迭代器。）

但是，如果我必须处理，整个事情就会有点失控列表数组或数组列表以及其他混合情况。

以最广泛、可能的方式编写算法的最优雅的方式是什么？

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

需要注意的一件事是，这比使用存在类型更好，因为在迭代器上调用 next 返回正确的类型，而不是 Seq[Any]。

这里有几个缺点：

• 如果容器不是所需类型的子类，则将其转换为一个，这会降低性能
• 算法不完全通用。我们需要将类型转换为 SeqLike 或 TraversableLike 只是为了使用这些类型提供的功能子集。因此制作转换函数可能很棘手。
• 如果某些功能在不同的上下文中可以有不同的解释怎么办？例如，矩形有两个“长度”属性（宽度和高度），

现在提供替代解决方案。我们注意到，我们实际上并不关心集合的类型，只关心它们的功能：

• TT 应该有 foldLeft、get(i: Int) （获取 head/tail )
• ST 应该有 length、get(i: Int) 和一个 Builder

所以我们可以对这些进行编码：（

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 不是必需的，因为它的实现是根据length 和 get，但我在这里添加了它，所以算法将翻译得更干净）

现在的算法是：

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

Scalaz 可能已经为您预定义了所有这些，不幸的是，我不太了解。

（我再次需要传递类型，因为推理不能推断出正确的类型）

好处是该算法现在完全通用，并且不需要从 Array 到 WrappedArray 的隐式转换才能使其工作

练习：定义对于元组;-)