scalafunctional-programmingcartesian-productcross-product

Cross product in Scala


I want to have a binary operator cross (cross-product/cartesian product) that operates with traversables in Scala:

val x = Seq(1, 2)
val y = List('hello', 'world', 'bye')
val z = x cross y    # i can chain as many traversables e.g. x cross y cross w etc

assert z == ((1, 'hello'), (1, 'world'), (1, 'bye'), (2, 'hello'), (2, 'world'), (2, 'bye'))

What is the best way to do this in Scala only (i.e. not using something like scalaz)?


Solution

  • 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.