抽象在集合 [英] abstracting over a collection
问题描述
最近，我为Anys的笛卡尔乘积写了一个迭代器，并从List 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组合（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笛卡尔（List（abc.toList，xy.toList，AB.toList））
// val ivvi = new笛卡尔（向量（10,20）））
val issi = new笛卡尔（Seq（Seq（1,2,3），Seq（10,20）））
// val iaai = new Cartesian数组（1,2,3），数组（10,20）））
（0到5）.foreach（dummy => println（illi.next（）））
//（0到5）.foreach（dummy => println（issi.next（）））
}
/ *
List（a，x，A）
列表（b，x，A）
列表（c，x，A）
列表（a，y，A）
c，y，A）
* /
代码适用于Seq和List它们是Seqs），但是当然不是用于数组或Vector，它们不是类型Seq，并且没有cons方法'::'。
但是逻辑也可以用于这样的集合。
我可以尝试向Vector和Array等Seq编写一个隐式转换，或者尝试编写一个自己的类似实现，或者写一个Wrapper，它将集合转换为Seq的Seq，并为内部集合调用hasNext和next，并将结果转换为Array，Vector或其他。 （我试图实现这种解决方法，但我必须认识到：这不是那么容易。对于真实世界的问题，我可能会独立地重写Iterator。）
如果我必须处理数组数组或数组列表和其他混合情况，整个事情会失去控制。
以最宽泛，可行的方式编写算法的最优雅的方法是什么？
有两种解决方案。第一个是不要求容器是一些通用超类的子类，而是可以转换为一个（通过使用隐式函数参数）。如果容器已经是所需类型的子类，则有一个预定义的标识转换，它只返回它。
import collection.mutable.Builder
import collection.TraversableLike
import collection.generic.CanBuildFrom
import collection.mutable.SeqLike
类笛卡尔[T，ST [T]，TT [S]]（val ll：TT [ST [T]]）（隐含cbf：CanBuildFrom [Nothing ，T [ST] [T]，seqLike：ST [T]，seqLike：ST [T] => SeqLike [T，ST [T] [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 $ b b}
def组合（xx：TT [ST [T]]，i：Int，builder：Builder [T，ST [T]]）：ST [T] =
if （xx.isEmpty）builder.result
else组合（xx.tail，i / xx.head.length，builder + = xx.head（i％xx.head.length））
}
这种作品：
scala>新的笛卡尔[String，Vector，Vector]（Vector（a），Vector（xy），Vector（AB））
res0：Cartesian [String，Vector，Vector]迭代器
scala> new笛卡尔[String，Array，Array]（Array（a），Array（xy），Array（AB）））
res1：Cartesian [String，Array，迭代器
我需要显式传递类型，因为bug https://issues.scala-lang.org/browse/SI-3343
$ b需要注意的是，这比使用存在类型更好，因为在迭代器上调用next会返回正确的类型，而不是Seq [Any]。
这里有几个缺点：
- 如果容器不是所需类型的子类，则转换为一个，
- 算法不完全通用。我们需要将类型转换为SeqLike或TraversableLike，只使用这些类型提供的一部分功能。所以制作转换函数可能很棘手。
- 如果某些功能在不同上下文中可以解释不同，该怎么办？例如，一个矩形有两个长度属性（宽度和高度）。
我们注意到，我们实际上并不关心收藏类型，只是他们的能力：
- TT应该有
foldLeft，get（i：Int）（获取头/尾） - code> length ，
get（i：Int）和一个Builder
所以我们可以编码这些：
trait HasGet [T，CC [_]] {
def get（cc：CC [T]，i：Int）：T
}
对象HasGet {
implicit def seqLikeHasGet [T，CC [X] < ;: SeqLike [X，_]] = new HasGet [T，CC] {
def get（cc：CC [T]，i：Int）：T = cc（i）
} b
$ b 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
}
对象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
}
$ b b）
trait HasFold [T，CC [_]] {
def foldLeft [A]（cc：CC [T]，zero：A） => A]：A
}
object HasFold {
implicit def seqLikeHasFold [T，CC [X] <：SeqLike [X，_]] = new HasFold [ CC] {
def foldLeft [A]（cc：CC [T]，零：A）（op：（A，T）=> A）：A = cc.foldLeft b $ b}
implicit def arrayHasFold [T] = new HasFold [T，Array] {
def foldLeft [A]（cc：Array [T]，zero：A） T）=> A）：A = {
var i = 0
var result = zero
while（i
i + = 1
}
结果
}
}
}
（严格来说，HasFold是不需要的，因为它的实现是在长度和get，但我添加它，所以算法将更清晰地翻译） / p>
现在的算法是：
class Cartesian [T，ST [ T]，stHasLength：HasLength [ST [T]]，stHasGet：HasGet [T]，T [ST]扩展迭代器[ST [T]]，TtHasLength：HasLength [TT [ST [T]]] {
def combicount（）：Int = ttHasFold.foldLeft（11,1）（（a，1）=> 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 $ b [x]：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>新的笛卡尔[String，Vector，List]（List（Vector（a），Vector（xy），Vector（AB）））
res6：Cartesian [String，Vector，List]迭代器
scala> new Cartesian [String，Array，Array]（Array（a），Array（xy），Array（AB）））
res7：Cartesian [String，迭代器
Scalaz可能已经为你预定义了所有这些，不幸的是，我不知道。
（再次需要传递类型，因为推断不会推断出正确的类型）
是算法现在完全通用，并且没有必要从Array到WrappedArray的隐式转换，以便它工作
Excercise：define for tuples ;-)
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)
}
}
And a client of that class:
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)
*/
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.
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) )
}
This sort of works:
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
I needed to explicitly pass the types because of bug https://issues.scala-lang.org/browse/SI-3343
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].
There are several drawbacks here:
- If the container is not a subclass of the required type, it is converted to one, which costs in performance
- The algorithm is not completely generic. We need types to be converted to SeqLike or TraversableLike only to use a subset of functionality these types offer. So making a conversion function can be tricky.
- What if some capabilities can be interpreted differently in different contexts? For example, a rectangle has two 'length' properties (width and height)
Now for the alternative solution. We note that we don't actually care about the types of collections, just their capabilities:
- 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
}
}
}
(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)
now the algorithm is:
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) ))
}
}
And use:
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 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)
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
Excercise: define for tuples ;-)
这篇关于抽象在集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
