Combining nested lists in Scala - flattened Carthesian product

Question

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.

score 9 · Accepted Answer · answered Sep 19 '13 at 10:48

9

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

answered Sep 19 '13 at 10:48

scand1sk

1,114
11
25

1

Note that it would be much more efficient (i.e., $n$ times more efficient, with $n$ being the size of the sublists of `listA`) to prepend the value `i` than to append it at the end of the list: `val listC = for (list <- listA; i <- listB) yield i :: list` – scand1sk Sep 19 '13 at 11:11
In my case the order is not important, so I will use the more efficient prepend operation as suggested. Thanks again! – ktorn Sep 19 '13 at 11:27

score 7 · Answer 2 · edited May 23 '17 at 11:56

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.

Thanks for your answer @travis-brown. Your alternative solution is also valuable to me, as I want to learn all things Scala. — ktorn, Sep 19 '13 at 12:29

Combining nested lists in Scala - flattened Carthesian product

2 Answers2