Cartesian product of two lists

by

The following suggestion is not using a for-comprehension. But I don’t think it’s a good idea after all, because as you noticed you’d be tied to a certain length of your cartesian product.

scala> def cartesianProduct[T](xss: List[List[T]]): List[List[T]] = xss match {
     |   case Nil => List(Nil)
     |   case h :: t => for(xh <- h; xt <- cartesianProduct(t)) yield xh :: xt
     | }
cartesianProduct: [T](xss: List[List[T]])List[List[T]]

scala> val conversion = Map('0' -> List("A", "B"), '1' -> List("C", "D"))
conversion: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map(0 -> List(A, B), 1 -> List(C, D))

scala> cartesianProduct("01".map(conversion).toList)
res9: List[List[java.lang.String]] = List(List(A, C), List(A, D), List(B, C), List(B, D))

Why not tail-recursive?

Note that above recursive function is not tail-recursive. This isn’t a problem, as xss will be short unless you have a lot of singleton lists in xss. This is the case, because the size of the result grows exponentially with the number of non-singleton elements of xss.

More Related Contents:

  1. Method parameters validation in Scala, with for comprehension and monads
  2. Composing Option with List in for-comprehension gives type mismatch depending on order
  3. Confused with the for-comprehension to flatMap/Map transformation
  4. Getting the desugared part of a Scala for/comprehension expression?
  5. withFilter instead of filter
  6. Scala “
  7. What are Scala context and view bounds?
  8. (Why) do we need to call cache or persist on a RDD
  9. Abort early in a fold
  10. How to pass -D parameter or environment variable to Spark job?
  11. Generating a class from string and instantiating it in Scala 2.10
  12. Why is “Unable to find encoder for type stored in a Dataset” when creating a dataset of custom case class?
  13. Append a column to Data Frame in Apache Spark 1.3
  14. MatchError while accessing vector column in Spark 2.0
  15. Spark: what’s the best strategy for joining a 2-tuple-key RDD with single-key RDD?
  16. How do I list all files in a subdirectory in scala?
  17. Mixing in a trait dynamically
  18. How to change setting inside SBT command?
  19. Scala: Implicit parameter resolution precedence
  20. Operate on neighbor elements in RDD in Spark
  21. Renaming column names of a DataFrame in Spark Scala
  22. Difference between fold and foldLeft or foldRight?
  23. Get TypeTag[A] from Class[A]
  24. In Scala, what exactly does ‘val a: A = _’ (underscore) mean?
  25. Spark: long delay between jobs
  26. How to wait for several Futures?
  27. forall in Scala
  28. assembly-merge-strategy issues using sbt-assembly
  29. How to create a Dataset of Maps?
  30. Spark ML VectorAssembler returns strange output

Leave a Comment