提取集合

| 最近，我为Anys的笛卡尔乘积编写了一个迭代器，并从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和List（它们是Seqs），但是当然不适用于数组或Vector，它们不是Seq类型，并且没有约束方法\':: \'。但是逻辑也可以用于此类集合。我可以尝试为Vector，Array等编写与Seq之间的隐式转换，或者尝试编写自己的类似实现，或者编写Wrapper，将包装转换为Seq的Seq，然后调用\'hasNext内部集合的\'和\'next \'，并将结果转换为Array，Vector或其他任何形式。（我尝试实现这种解决方法，但我必须认识到：这并不容易。对于现实世界中的问题，我可能会独立地重写Iterator。）但是，如果我必须处理列表数组或数组列表以及其他混合情况，那么整个事情就会失去控制。用最广泛，可能的方式编写算法的最优雅方法是什么？

已邀请:

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。因此，制作转换函数可能很棘手。如果某些功能可以在不同的上下文中进行不同的解释怎么办？例如，一个矩形具有两个\'length \'属性（宽度和高度）现在为替代解决方案。我们注意到，我们实际上并不关心集合的类型，而只是关心它们的功能： TT应该有foldLeft，get(i: Int)（头/尾） 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不是必需的，因为它的实现是基于长度和获取的，但是我在这里添加了它，以便算法可以更清晰地转换）现在的算法是：

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的隐式转换即可运行锻炼：为元组定义;-)

要回复问题请先登录或注册

提取集合

1 个回复

发起人

abstraction

collections

scala

问题状态

提取集合

与内容相关的链接

1 个回复

发起人

abstraction

collections

scala

问题状态