Scala Recursive For Comprehension Prepends Empty List Only Once, Why?

There is nothing producing an empty list inside this for comprehension. Even if

combinations(occurrences filter {case (c, _) => c > char})

contained an empty list and returned it in rest <- ... (it should for the first element), a value is prepended in List((char, count)) ++ rest making it non-empty by design.

So the whole for-comprehension must return a List of non-empty Lists to which an empty list is prepended.

This basically builds solution by induction:

• if you have an empty list - return an empty list because it is a valid solution for this input
• if you start with (char, maxOccurrences) :: rest
  • assume that you have a valid solution for combinations(rest)
  • then take each such solution and add (char, 1) to each element of rest,
  • then take each such solution and add (char, 2) to each element of rest,
  • ...
  • then take each such solution and add (char, maxOccurrences) to each element of rest
  • then combine all of these results into one solution
  • all of these are non-empty because you always prepended something
  • so you are missing empty set, so you add it explicitly to all the other solutions combined to create a complete solution for (char, maxOccurrences) :: rest

Because you have a valid starting point and a valid way of creating next step from the previous, you know that you can always create a valid solution.

In the for comprehension

  def combinations(occurrences: Occurrences): List[Occurrences] =
    List() :: (for {
      (char, max) <- occurrences
      count <- 1 to max
      rest <- combinations(occurrences filter {case (c, _) => c > char})
    } yield List((char, count)) ++ rest)

is doing the same thing as

def combinations(occurrences: Occurrences): List[Occurrences] =
  List() :: occurrences.flatMap { case (char, max) =>
    (1 to map).flatMap { count =>
      combinations(occurrences filter {case (c, _) => c > char}).map { rest =>
        (char, count) :: rest
      }
    }
  }

which is the same as

def combinations(occurrences: Occurrences): List[Occurrences] =
  occurrences.map { case (char, max) =>
    (1 to map).map { count =>
      val newOccurence = (char, count)
      combinations(occurrences filter {case (c, _) => c > char}).map { rest =>
        newOccurence :: rest
      }
    }
  }.flatten.flatten.::(List())

and this you can easily compare to the induction recipe from above:

def combinations(occurrences: Occurrences): List[Occurrences] =
  occurrences.map { case (char, max) =>
    // for every character on the list of occurrences
    (1 to max).map { count =>
      // you construct (char, 1), (char, 2), ... (char, max)
      val newOccurence = (char, count)
      // and for each such occurrence
      combinations(occurrences filter {case (c, _) => c > char}).map { rest =>
        // you prepend it into every result from smaller subproblem
        newOccurence :: rest
      }
    }
  }
   // because you would have a List(List(List(List(...)))) here
   // and you need List(List(...)) you flatten it twice
  .flatten.flatten
  // and since you are missing empty result, you prepend it here
  .::(List())

The solution you posted does exactly the same thing just in more compacted way - instead of .map().flatten, there are .flatMaps hidden by a for-comprehension.

I think that tracking the calls will help you understand it better. I am going to number the steps to easily going back and forth between them.

1. combinations(List(('a', 2), ('b', 2))), we have first:

   (char, max) <- ('a', 2)
   count <- 1
   

   The result of occurrences filter {case (c, _) => c > char} will be List(('b', 2)).

2. Therefore we now calculate combinations(List(('b', 2))):

   (char, max) <- ('b', 2)
   count <- 1
   

   Now, the result of occurrences filter {case (c, _) => c > char} will be List().

3. We are going to calculate combiantions(List()):

   The for comprehension will be List(), and List() :: List() results in List(). Therefore we are back in step 2:

4. (step 2) We had:

   (char, max) <- ('b', 2)
   count <- 1
   

   and now we have no elements for rest. So the result of step 2 will be List() :: List() which is List() as well. Back to step 1. So we are going to yield for that option List((char, count)) ++ rest) which is: List(('b', 1)) ++ List()) which is List(('b', 1)) We are now in the next iteration of the same call with:

   (char, max) <- ('b', 2)
   count <- 2
   

   rest will be List() again and we are now going to yield for that option List((char, count)) ++ rest) which is: List(('b', 2)) ++ List()) which is List(('b', 2)). Now we have to add the empty list, and the result is: List(List(), List((b,1)), List((b,2))).

5. (step 1) We had:

   (char, max) <- ('a', 2)
   count <- 1
   

   and now we have:

   rest <- List()
   

   So we are yielding List((char, count)) ++ rest which is: List(('a', 1)) ++ List() which is: List(('a', 1))

   Now we continue to:

   rest <- List((b,1))
   

   So we are yielding List((char, count)) ++ rest which is: List(('a', 1)) ++ List((b,1)) which is: List(('a', 1), ('b', 1)).

   Now we continue to:

   rest <- List((b,2))
   

   So we are yielding List((char, count)) ++ rest which is: List(('a', 1)) ++ List((b,2)) which is: List(('a', 1), ('b', 2)). The aggregated result so far is:

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

Now max is going to be increase to 2, and we are going to do the same calculation in steps 2-4, which are going to yield, with the exact same logic:

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

And now (char, max) is going to be changed into ('b', 2), which will result it(after applying the same logic from steps 2-4):

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

When aggregating all together, with the prior empty list we get the wanted output.

What really helps to see what I just explained, is adding printing messages:

def combinations(occurrences: Occurrences): List[Occurrences] = {
  println("Starting with: " + occurrences)
  val result = List() :: (for {
    (char, max) <- occurrences
    count <- 1 to max
    rest <- combinations(occurrences filter {case (c, _) => c > char })
  } yield {
    val result = List((char, count)) ++ rest
    println("Occurrences are: " + occurrences + " Result is: " + result)
    result
  })
  println("Done with: " + occurrences + " results are: " + result)
  result
}

Then the call println("Done: " + combinations(List(('a', 2), ('b', 2)))) results in:

Starting with: List((a,2), (b,2))
Starting with: List((b,2))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,1))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,2))
Done with: List((b,2)) results are: List(List(), List((b,1)), List((b,2)))
Occurrences are: List((a,2), (b,2)) Result is: List((a,1))
Occurrences are: List((a,2), (b,2)) Result is: List((a,1), (b,1))
Occurrences are: List((a,2), (b,2)) Result is: List((a,1), (b,2))
Starting with: List((b,2))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,1))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,2))
Done with: List((b,2)) results are: List(List(), List((b,1)), List((b,2)))
Occurrences are: List((a,2), (b,2)) Result is: List((a,2))
Occurrences are: List((a,2), (b,2)) Result is: List((a,2), (b,1))
Occurrences are: List((a,2), (b,2)) Result is: List((a,2), (b,2))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((a,2), (b,2)) Result is: List((b,1))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((a,2), (b,2)) Result is: List((b,2))
Done with: List((a,2), (b,2)) results are: List(List(), List((a,1)), List((a,1), (b,1)), List((a,1), (b,2)), List((a,2)), List((a,2), (b,1)), List((a,2), (b,2)), List((b,1)), List((b,2)))
Done: List(List(), List((a,1)), List((a,1), (b,1)), List((a,1), (b,2)), List((a,2)), List((a,2), (b,1)), List((a,2), (b,2)), List((b,1)), List((b,2)))