Geek Answers Handbook

Abstract collection

I recently wrote an iterator for the Cartesian product Anys and started with the List of List, but admitted that I can easily switch to the more abstract Seq tag.

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 the client of this 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 certainly not for arrays or vectors that are not of type Seq and do not have the cons-method '::'.

But logic can be used for such collections.

I could try writing an implicit conversion to and from Seq for Vector, Array, etc. or try to write your own similar implementation or write Wrapper, which converts the collection to Seq of Seq and calls 'hasNext' and 'next' for the internal collection and converts the result to Array, Vector or something else. (I tried to implement such workarounds, but I have to admit: it's not that simple. For a real problem, I would probably rewrite Iterator independently.)

However, all this will get a little 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 an algorithm in the widest possible way?

+2
source share
1 answer

There are two solutions. The first is to not require the containers to be a subclass of some generic superclass, but be converted to one (using the implicit function arguments). If the container is already a subclass of the required type, there is a predefined identity transformation that 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 type of work:

 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 types due to an error https://issues.scala-lang.org/browse/SI-3343

It should be noted that this is better than using existential types, because calling next on the iterator returns the correct type, 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 performance
  • The algorithm is not completely general. We need types that need to be converted to SeqLike or TraversableLike, only to use the subset of the functionality offered by these types. Therefore, conversion can be difficult.
  • What if some features can be interpreted differently in different contexts? For example, a rectangle has two length properties (width and height)

Now for an alternative solution. We note that we really do not care about the types of collections, but only about their capabilities:

  • TT must have foldLeft , get(i: Int) (to get head / tail)
  • ST must have length , get(i: Int) and Builder

So we can encode them:

 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 to make the algorithm translate more cleanly)

now the algorithm:

 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 all this is predetermined for you, unfortunately, I do not know very well.

(again I need to pass types because the output does not output the correct view)

The advantage is that the algorithm is now completely general and that there is no need for implicit conversions from the array to WrappedArray to make it work

Exercise: definition for tuples; -)

+2
source

More articles:


All Articles