How to write tuple range function in scala?

Question

I want following function range((1,1), (2,2)) which return

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

It is analog for one dimensional range with 1 to 2

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

I've 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've chosen wrong direction.

Your type signature in the second line should be `Seq[(Int,Int)]`, no? — ziggystar, Oct 03 '11 at 12:20
In general functions don't work "for any tuple (arity)". Tuples don't generalize over their size. And since you are enforcing that every tuple element has the same type, why not choose a collection instead? — ziggystar, Oct 03 '11 at 12:22
@ziggystar you are right bad design leads to problems in implementation — yura, Oct 03 '11 at 14:20

score 7 · Accepted Answer · answered Oct 03 '11 at 13:00

I'd suggest the same thing that @ziggystar suggested above. Use List[Int] instead of tuples of Ints.

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))

This implementation assumes that xs and ys are ordered and have same length.

score 4 · Answer 2 · answered Oct 03 '11 at 12:38

First, consider this:

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

It'd be nice to have something like that 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 that work for you?

Why yield a map? Just add a second generator from `a2` to `b2`. Besides, this is wrong. If `a1 != a2` or `b1 != b2`, you'll get wrong results (though that's easily fixable). — Daniel C. Sobral, Oct 03 '11 at 13:14

score 2 · Answer 3 · answered Oct 03 '11 at 12:32

You'll need a different version for each tuple-arity (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 as:

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

Luigi Plinge · Answer 4 · 2011-10-03T22:36:01.653

Simple way with lots of cut and paste, overload the method for each tuple arity:

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

Alternatively:

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 basic problem is that since Scala is statically typed, the method needs to have a return type, so you can never have a single method that returns both a Seq[(Int, Int)] and a Seq[(Int, Int, Int)] and all the other arities of tuple. The best you can do is to use the closest type that covers all of the outputs, in this case Product with Serializable. You can of course do a cast on the result e.g. res0.map(_.asInstanceOf[(Int, Int, Int)]).

Overloading the method as in the first example allows you a different return type for each arity, so you don't need to do any casting.

score 1 · Answer 5 · edited May 23 '17 at 10:34

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

Here is a class Cartesian, which 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))
}

usage:

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))

How to write tuple range function in scala?

5 Answers5