How to write a tuple range function in scala?

Question

I need the following function range((1,1), (2,2)) that return

 Seq[(Int,Int)]((1,1),(1,2),(2,1),(2,2)) 

It is an analog for the one-dimensional range from 1 to 2

The function should work for any scala tuple (i.e. Tuple2, Tuple3, Tuple4, ...) and be typical.

I tried with

  def tupleRange[T <: Product](t1:T, t2:T):Seq[T] = { assert(t1.productArity == t2.productArity) def tail(t:Product):Product = sys.error("todo"); def join(i:Int, p:Product):T = sys.error("todo"); for( v <- t1.productElement(0).asInstanceOf[Int] to t2.productElement(0).asInstanceOf[Int]; v2 <- tupleRange(tail(t1), tail(t2))) yield join(v,v2) } implicit def range[T <:Product](p1:T) = new { def to(p2:T) = tupleRange(p1,p2)} 

But I think I chose the wrong direction.

Answer 1

I suggest the same as @ziggystar suggested above. Use List[Int] instead of Int s tuples.

 scala> import scalaz._ import scalaz._ scala> import Scalaz._ import Scalaz._ scala> def range(xs: List[Int], ys: List[Int]): List[List[Int]] = { | (xs, ys).zipped.map((x, y) => List.range(x, y + 1)).sequence | } range: (xs: List[Int], ys: List[Int])List[List[Int]] scala> range(List(1, 2, 4), List(2, 5, 6)) res29: List[List[Int]] = List(List(1, 2, 4), List(1, 2, 5), List(1, 2, 6), List(1, 3, 4), List(1, 3, 5), List(1, 3, 6), List(1, 4, 4), List(1, 4, 5), List(1, 4, 6), List(1, 5, 4), List(1, 5, 5), List(1, 5, 6), List(2, 2, 4), List(2, 2, 5), List(2, 2, 6), List(2, 3, 4), List(2, 3, 5), List(2, 3, 6), List(2, 4, 4), List(2, 4, 5), List(2, 4, 6), List(2, 5, 4), List(2, 5, 5), List(2, 5, 6)) 

In this implementation, it is assumed that xs and ys ordered and have the same length.

Answer 2

First, consider the following:

 scala> 1 to 10 res0: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) 

It would be nice to have something like this for Tuples, right?

 class RangedTuple(t: Tuple2[Int, Int]) { def to(t2: Tuple2[Int, Int]) = { (t, t2) match { case ((a1: Int, a2: Int), (b1: Int, b2: Int)) => { (for { i <- a1 to b1 } yield (a1 to b1).map(j => (i, j))).flatMap(k => k) } } } } implicit def t2rt(t: Tuple2[Int, Int]) = new RangedTuple(t) 

This gives you the following:

 scala> (1, 1) to (2, 2) res1: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (2,1), (2,2)) scala> (1, 1) to (3, 3) res2: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)) 

Does this work for you?

Answer 3

You will need a different version for each tuple (but you can use a preprocessor to generate each version). Here is my implementation (which is lazy):

 def range2( range: Range ): Seq[(Int,Int)] = range.toStream.map( i => (i,i) ) 

You can use it like:

 scala> range2( 1 to 10 ) res3: Seq[(Int, Int)] = Stream((1,1), ?) 

Answer 4

A simple way with a lot of cut and paste, overload the method for each attribute of the tuple:

 def range(r: (Int, Int), s: (Int, Int)) = for { p1 <- r._1 to s._1 p2 <- r._2 to s._2 } yield (p1, p2) def range(r: (Int, Int, Int), s: (Int, Int, Int)) = for { p1 <- r._1 to s._1 p2 <- r._2 to s._2 p3 <- r._3 to s._3 } yield (p1, p2, p3) def range(r: (Int, Int, Int, Int), s: (Int, Int, Int, Int)) = for // etc up to 22 

As an alternative:

 def range(p1: Product, p2: Product) = { def toList(t: Product): List[Int] = t.productIterator.toList.map(_.asInstanceOf[Int]) def toProduct(lst: List[Int]) = lst.size match { case 1 => Tuple1(lst(0)) case 2 => Tuple2(lst(0), lst(1)) case 3 => Tuple3(lst(0), lst(1), lst(2)) //etc up to 22 } def go(xs: List[Int], ys: List[Int]): List[List[Int]] = { if(xs.size == 1 || ys.size == 1) (xs.head to ys.head).toList.map(List(_)) else (xs.head to ys.head).toList.flatMap(i => go(xs.tail, ys.tail).map(i :: _)) } go(toList(p1), toList(p2)) map toProduct } 

seems to work:

 scala> range((1,2,4), (2,5,6)) res66: List[Product with Serializable] = List((1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5), (1,3,6), (1,4,4), (1,4,5), (1,4,6), (1,5,4), (1,5,5), (1,5,6), (2,2,4), (2,2,5), (2,2,6), (2,3,4), (2,3,5), (2,3,6), (2,4,4), (2,4,5), (2,4,6), (2,5,4), (2,5,5), (2,5,6)) 

Your main problem is that since Scala is statically typed, the method must have a return type, so you can never have a single method that returns both Seq[(Int, Int)] and Seq[(Int, Int, Int)] and all other tuple objects. The best you can do is use the closest type that spans all outputs, in this case Product with Serializable . You can, of course, make a throw at the result, for example. res0.map(_.asInstanceOf[(Int, Int, Int)]) .

Method overloading, as in the first example, allows you to use a different type of return value for each arity, so you do not need to do casting.

Answer 5

How about an Iterator and using two Seq instead of two tuples for initialization?

The following is a Cartesian class that extends Iterator .

 def rangeIterator (froms: Seq[Int], tos: Seq[Int]) = { def range (froms: Seq[Int], tos: Seq[Int]) : Seq[Seq[Int]] = if (froms.isEmpty) Nil else Seq (froms.head to tos.head) ++ range (froms.tail, tos.tail) new Cartesian (range (froms, tos)) } 

using:

 scala> val test = rangeIterator (Seq(1, 1), Seq(2, 2)) test: Cartesian = non-empty iterator scala> test.toList res38: List[Seq[_]] = List(List(1, 1), List(2, 1), List(1, 2), List(2, 2)) scala> val test = rangeIterator (Seq(1, 0, 9), Seq(2, 2, 11)) test: Cartesian = non-empty iterator scala> test.toList res43: List[Seq[_]] = List(List(1, 0, 9), List(2, 0, 9), List(1, 1, 9), List(2, 1, 9), List(1, 2, 9), List(2, 2, 9), List(1, 0, 10), List(2, 0, 10), List(1, 1, 10), List(2, 1, 10), List(1, 2, 10), List(2, 2, 10), List(1, 0, 11), List(2, 0, 11), List(1, 1, 11), List(2, 1, 11), List(1, 2, 11), List(2, 2, 11))