How to write universal combination in Scala

Question

I have a simple combination function in Scala:

def combine(t1: List[Int], t2: List[Int]) = {
        for {
            a1 <- t1
            a2 <- t2
        } yield List((1, a1), (2, a2))
    }

which for given

List(1, 2), List(3, 4)

returns

List( List( (1,1), (2,3) ), List( (1,1), (2,4) ), List( (1,2), (2,3) ), List( (1,2), (2,4) ) )

So I'd like to have list of combinations (tuples) in which first element is an index and the second one is value from domain. I want to have this combination unique so that there is no combination with tuples of two the same indexes.

Unfortunately I don't know how many lists I'll get to combine.
How to write more universal function?

Answer 1

If I understood the question correctly, each entry of the resulting list should be a List with as many tuples in it as there are elements in the original List. That is, I think you are basically asking how to write a "variable-length for-comprehension," one where the number of generators needed depends on the arguments.

To do that you might as well just think about what the for-comprehension desugars to and then make a recursive version of it, like so:

$ cat x.scala
object X extends App {

  // Some lists.
  val t1 = List(1,2)
  val t2 = List(4,5,6)
  val t3 = List(7,8)

  // What I think you expect the output to look like for three lists.
  val result1 =  for ( a1<-t1; a2<-t2; a3<-t3 ) yield List( (1,a1), (2,a2), (3,a3) )
  println(result1)

  // Here's what that desugars to.
  val result2 = t1 flatMap ( a1 => t2 flatMap( a2 => t3 map( a3 => List( (1,a1), (2,a2), (3,a3) ) ) ) )
  println(result2)
  println( result2 == result1 )

  // Here is how to do the same thing when you don't know how many lists there are.
  // We're going to assume there is at least one; you could of course add a check.
  def combine( lists:List[List[Int]], i:Int=1, soFar:List[(Int,Int)]=Nil ):List[List[(Int,Int)]] =
    lists match {
      case head::Nil  =>  head.map    ( x => ( (i,x)::soFar ).reverse )
      case head::rest =>  head.flatMap( x => combine( rest, i+1, (i,x)::soFar ) )
    }

  // Now let's see if that gives us the same answer.
  val result3 = combine( List(t1,t2,t3) )
  println(result3)
  println( result3 == result1 )

}
$ scalac x.scala
$ scala X       
List(List((1,1), (2,4), (3,7)), List((1,1), (2,4), (3,8)), List((1,1), (2,5), (3,7)), List((1,1), (2,5), (3,8)), List((1,1), (2,6), (3,7)), List((1,1), (2,6), (3,8)), List((1,2), (2,4), (3,7)), List((1,2), (2,4), (3,8)), List((1,2), (2,5), (3,7)), List((1,2), (2,5), (3,8)), List((1,2), (2,6), (3,7)), List((1,2), (2,6), (3,8)))
List(List((1,1), (2,4), (3,7)), List((1,1), (2,4), (3,8)), List((1,1), (2,5), (3,7)), List((1,1), (2,5), (3,8)), List((1,1), (2,6), (3,7)), List((1,1), (2,6), (3,8)), List((1,2), (2,4), (3,7)), List((1,2), (2,4), (3,8)), List((1,2), (2,5), (3,7)), List((1,2), (2,5), (3,8)), List((1,2), (2,6), (3,7)), List((1,2), (2,6), (3,8)))
true
List(List((1,1), (2,4), (3,7)), List((1,1), (2,4), (3,8)), List((1,1), (2,5), (3,7)), List((1,1), (2,5), (3,8)), List((1,1), (2,6), (3,7)), List((1,1), (2,6), (3,8)), List((1,2), (2,4), (3,7)), List((1,2), (2,4), (3,8)), List((1,2), (2,5), (3,7)), List((1,2), (2,5), (3,8)), List((1,2), (2,6), (3,7)), List((1,2), (2,6), (3,8)))
true