对集合进行抽象 [英] abstracting over a collection
问题描述
最近，我为 Anys 的笛卡尔积编写了一个迭代器，并从 List 的 List 开始，但认识到，我可以轻松切换到更抽象的 trait Seq.
Recently, I wrote an iterator for a cartesian product of Anys, and started with a List of List, but recognized, that I can easily switch to the more abstract trait Seq.
我知道，你喜欢看代码.:)
I know, you like to see the code. :)
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 方法::"的数组或向量.
The code works well for Seq and Lists (which are Seqs), but of course not for Arrays or Vector, which aren't of type Seq, and don't have a cons-method '::'.
但该逻辑也可用于此类集合.
But the logic could be used for such collections too.
我可以尝试为 Vector、Array 等编写与 Seq 之间的隐式转换，或者尝试编写自己的类似实现，或者编写一个 Wrapper，它将集合转换为 Seq 的 Seq，并调用'hasNext' 和 'next' 用于内部集合，并将结果转换为数组、向量或其他任何内容.(我试图实现这样的变通方法，但我必须认识到:这并不容易.对于现实世界的问题，我可能会独立地重写迭代器.)
I could try to write an implicit conversion to and from Seq for Vector, Array, and such, or try to write an own, similar implementation, or write an Wrapper, which transforms the collection to a Seq of Seq, and calls 'hasNext' and 'next' for the inner collection, and converts the result to an Array, Vector or whatever. (I tried to implement such workarounds, but I have to recognize: it's not that easy. For a real world problem I would probably rewrite the Iterator independently.)
但是，如果我必须处理列表数组或数组列表以及其他混合情况，整个事情就会有点失控.
However, the whole thing get's a bit out of control if I have to deal with Arrays of Lists or Lists of Arrays and other mixed cases.
以最广泛、可能的方式编写算法的最优雅方式是什么?
What would be the most elegant way to write the algorithm in the broadest, possible way?
推荐答案
有两种解决方案.第一个是不要求容器是某个通用超类的子类，而是可以转换为一个(通过使用隐式函数参数).如果容器已经是所需类型的子类，则有一个预定义的标识转换，它只返回它.
There are two solutions. The first is to not require the containers to be a subclass of some generic super class, but to be convertible to one (by using implicit function arguments). If the container is already a subclass of the required type, there's a predefined identity conversion which only returns it.
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
I needed to explicitly pass the types because of bug https://issues.scala-lang.org/browse/SI-3343
需要注意的一点是，这比使用存在类型要好，因为在迭代器上调用 next 会返回正确的类型，而不是 Seq[Any].
One thing to note is that this is better than using existential types, because calling next on the iterator returns the right type, and not Seq[Any].
这里有几个缺点:
- 如果容器不是所需类型的子类，则将其转换为一个，这会降低性能
- 该算法并非完全通用.我们需要将类型转换为 SeqLike 或 TraversableLike 仅使用这些类型提供的功能子集.因此，制作转换函数可能很棘手.
- 如果某些功能在不同的上下文中可以有不同的解释怎么办?例如，一个矩形有两个长度"属性(宽度和高度)
现在是替代解决方案.我们注意到我们实际上并不关心集合的类型，只关心它们的功能:
Now for the alternative solution. We note that we don't actually care about the types of collections, just their capabilities:
- TT 应该有
foldLeft,get(i: Int)(得到头/尾) - ST 应该有
length、get(i: Int)和一个 Builder
- TT should have
foldLeft,get(i: Int)(to get head/tail) - ST should have
length,get(i: Int)and a Builder
所以我们可以编码这些:
So we can encode these:
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 不是必需的，因为它的实现是在长度和获取方面，但我在这里添加了它，所以算法会更清晰地翻译)
(strictly speaking, HasFold is not required since its implementation is in terms of length and get, but i added it here so the algorithm will translate more cleanly)
现在的算法是:
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 可能已经为您预定义了所有这些，不幸的是，我不太了解.
Scalaz probably has all of this predefined for you, unfortunately, I don't know it well.
(我再次需要传递类型，因为推断不能推断出正确的类型)
(again I need to pass the types because inference doesn't infer the right kind)
好处是该算法现在是完全通用的，并且不需要从 Array 到 WrappedArray 的隐式转换以使其工作
The benefit is that the algorithm is now completely generic and that there is no need for implicit conversions from Array to WrappedArray in order for it to work
练习:定义元组;-)
这篇关于对集合进行抽象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
