CODEWITHSUNDEEP
scala
ktorn
ktorn

Reputation: 88

Combining nested lists in Scala - flattened Carthesian product

I have an interesting problem which is proving difficult for someone new to Scala.
I need to combine 2 lists:

listA : List[List[Int]]
listB : List[Int]

In the following way:

val listA = List(List(1,1), List(2,2))
val listB = List(3,4)
val listC = ???

// listC: List[List[Int]] = List(List(1,1,3),List(1,1,4),List(2,2,3),List(2,2,4)

In Java, I would use a couple of nested loops:

for(List<Integer> list : listA) {
    for(Integer i: listB) {
        subList = new ArrayList<Integer>(list);
        subList.add(i);
        listC.add(subList);
    }
}

I'm guessing this is a one liner in Scala, but so far it's eluding me.

Upvotes: 3

Views: 1060

Answers (2)

Travis Brown
Travis Brown

Reputation: 139038

scand1sk's answer is almost certainly the approach you should be using here, but as a side note, there's another way of thinking about this problem. What you're doing is in effect lifting the append operation into the applicative functor for lists. This means that using Scalaz you can write the following:

import scalaz._, Scalaz._

val listC = (listA |@| listB)(_ :+ _)

We can think of (_ :+ _) as a function that takes a list of things, and a single thing of the same type, and returns a new list:

(_ :+ _): ((List[Thing], Thing) => List[Thing])

Scalaz provides an applicative functor instance for lists, so we can in effect create a new function that adds an extra list layer to each of the types above. The weird (x |@| y)(_ :+ _) syntax says: create just such a function and apply it to x and y. And the result is what you're looking for.

And as in the for-comprehension case, if you don't care about order, you can make the operation more efficient by using :: and flipping the order of the arguments.

For more information, see my similar answer here about the cartesian product in Haskell, this introduction to applicative functors in Scala, or this blog post about making the syntax for this kind of thing a little less ugly in Scala. And of course feel free to ignore all of the above if you don't care.

Upvotes: 7

scand1sk
scand1sk

Reputation: 1124

You want to perform a flattened Cartesian product. For-comprehensions are the easiest way to do this and may look similar to your Java solution:

val listC = for (list <- listA; i <- listB) yield list :+ i

Upvotes: 9

Related Questions