Producto cruzado en Scala
Quiero tener un operador binario cross
(producto cruzado / producto cartesiano) que opere 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, no usar algo como scalaz)?
5 answers
Puedes hacer esto bastante directamente con una clase implícita y una for
-comprensión 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 la versión 2.10, pero no tan conciso, ya que tendría que 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 quieres que xs cross ys cross zs
devuelva un Tuple3
, sin embargo, necesitarás una gran cantidad de repeticiones o una biblioteca como Sin forma.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-06 22:45:34
Aquí está la implementación del producto cruzado recursivo de un número arbitrario de listas:
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))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-07 17:12:46
Cruzar x_list
y y_list
con:
val cross = x_list.flatMap(x => y_list.map(y => (x, y)))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-09 06:39:37
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))
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-12-06 17:17:02
Aquí hay algo similar a la respuesta de Milad, pero no recursiva.
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 entrada de blog.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-04-30 17:31:02