for comprehension in scala with recursive call

Question

I am working on the last project for the coursera course "functional programming in scala". I need to implement a function called combinations that takes a list of character occurrences and output all possible subsets of character occurrences. As an example, the subsets of the occurrence list List(('a', 2), ('b', 2)) are:

List(
  List(),
  List(('a', 1)),
  List(('a', 2)),
  List(('b', 1)),
  List(('a', 1), ('b', 1)),
  List(('a', 2), ('b', 1)),
  List(('b', 2)),
  List(('a', 1), ('b', 2)),
  List(('a', 2), ('b', 2))
)

My approach to this problem is to loop through each character (such as 'a'), and take its possible occurrence counts (from 0 to 2), and prepand this to the current subset. Then proceed to the next character and repeat until I hit the end of the list, which is caught by the base case. I implemented this with a for comprehension like below:

type Occurrences = List[(Char, Int)]

def combinations(occurrences: Occurrences): List[Occurrences] =
  if (occurrences == List()) List() // base case
  else
    for {
      (c, n) <- occurrences
      subc <- combinations((occurrences.toMap - c).toList)
      i <- 0 to n
    } yield {
      if (i == 0) subc // not including c in the subset
      else (c, i) :: subc // including c in the subset
    }

This function always gives me an empty list when I call combinations(List(('a', 2), ('b', 2)). Any ideas why this is the case?

Answer 1

The reason for the unexpected output is here:

subc <- combinations((occurrences.toMap - c).toList)

This will recurse, loading the stack frame, until eventually returning the base case List(). Now, remember that in a for comprehension the generators (<-) are implemented via map or flatMap, and once you map on an empty collection you're done.

List[Int]().map(_ + 1).foreach(_ => println("got it"))  // no output

So the following generator, i <- 0 to n, is not invoked, there is nothing to yield and the empty List() is the only thing to return. Then the stack frame pops, the empty List() is received, etc.

Answer 2

The problem is the line:

subc <- combinations((occurrences.toMap - c).toList)

In the call just above the base case, this is evaluated to List() which hamstrings your for-comprehension:

scala> for {a <- 0 to 3; b <- List()} yield a
res0: scala.collection.immutable.IndexedSeq[Int] = Vector()

Which makes that call return List() and so on, meaning that you are returning empty lists all the way up the call stack, which is why you get a List() at the top.