Cross product in Scala

Solution 1:

You can do this pretty straightforwardly with an implicit class and a for-comprehension in Scala 2.10:

implicit class Crossable[X](xs: Traversable[X]) {
  def cross[Y](ys: Traversable[Y]) = for { x <- xs; y <- ys } yield (x, y)
}

val xs = Seq(1, 2)
val ys = List("hello", "world", "bye")

And now:

scala> xs cross ys
res0: Traversable[(Int, String)] = List((1,hello), (1,world), ...

This is possible before 2.10—just not quite as concise, since you'd need to define both the class and an implicit conversion method.

You can also write this:

scala> xs cross ys cross List('a, 'b)
res2: Traversable[((Int, String), Symbol)] = List(((1,hello),'a), ...

If you want xs cross ys cross zs to return a Tuple3, however, you'll need either a lot of boilerplate or a library like Shapeless.

Solution 2:

cross x_list and y_list with:

val cross = x_list.flatMap(x => y_list.map(y => (x, y)))

Solution 3:

Here is the implementation of recursive cross product of arbitrary number of lists:

def crossJoin[T](list: Traversable[Traversable[T]]): Traversable[Traversable[T]] =
  list match {
    case xs :: Nil => xs map (Traversable(_))
    case x :: xs => for {
      i <- x
      j <- crossJoin(xs)
    } yield Traversable(i) ++ j
  }

crossJoin(
  List(
    List(3, "b"),
    List(1, 8),
    List(0, "f", 4.3)
  )
)

res0: Traversable[Traversable[Any]] = List(List(3, 1, 0), List(3, 1, f), List(3, 1, 4.3), List(3, 8, 0), List(3, 8, f), List(3, 8, 4.3), List(b, 1, 0), List(b, 1, f), List(b, 1, 4.3), List(b, 8, 0), List(b, 8, f), List(b, 8, 4.3))