Producto cruzado en Scala

functional-programming cartesian-product

Question

Quiero tener un operador binario cross (producto cruzado / producto cartesiano) que opera con traversables en 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''))

¿Cuál es la mejor manera de hacer esto solo en Scala (es decir, sin usar algo como Scalaz)?

Answer 1

Aquí está la implementación del producto cruzado recursivo de una cantidad arbitraria de listas:

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

Answer 2

Aquí hay algo similar a la respuesta de Milad , pero no recursivo.

def cartesianProduct[T](seqs: Seq[Seq[T]]): Seq[Seq[T]] = {
  seqs.foldLeft(Seq(Seq()).asInstanceOf[Seq[Seq[T]]])((b, a) => b.flatMap{ i => a.map(j => i ++ Seq(j)) })
}

Basado en esta publicación de blog .

Answer 3

Puedes hacer esto de forma bastante directa con una clase implícita y una comprensión for defecto en 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")

Y ahora:

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

Esto es posible antes de 2.10, pero no del todo concisa, ya que necesitaría definir tanto la clase como un método de conversión implícito.

También puedes escribir esto:

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

Si quiere xs cross ys cross zs para devolver un Tuple3 , sin embargo, necesitará una gran repetición o una biblioteca como Shapeless .

Answer 4

cruzar x_list y y_list con:

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

Answer 5

class CartesianProduct(product: Traversable[Traversable[_ <: Any]]) {
  override def toString(): String = {
    product.toString
  }

  def *(rhs: Traversable[_ <: Any]): CartesianProduct = {
      val p = product.flatMap { lhs =>
        rhs.map { r =>
          lhs.toList :+ r
        }
      }

      new CartesianProduct(p)
  }
}

object CartesianProduct {
  def apply(traversable: Traversable[_ <: Any]): CartesianProduct = {
    new CartesianProduct(
      traversable.map { t =>
        Traversable(t)
      }
    )
  }
}

// TODO: How can this conversion be made implicit?
val x = CartesianProduct(Set(0, 1))
val y = List("Alice", "Bob")
val z = Array(Math.E, Math.PI)

println(x * y * z) // Set(List(0, Alice, 3.141592653589793), List(0, Alice, 2.718281828459045), List(0, Bob, 3.141592653589793), List(1, Alice, 2.718281828459045), List(0, Bob, 2.718281828459045), List(1, Bob, 3.141592653589793), List(1, Alice, 3.141592653589793), List(1, Bob, 2.718281828459045))

// TODO: How can this conversion be made implicit?
val s0 = CartesianProduct(Seq(0, 0))
val s1 = Seq(0, 0)

println(s0 * s1) // List(List(0, 0), List(0, 0), List(0, 0), List(0, 0))