Help with this for comprehension loop - HALF SOLVED

#1

Hi

I’ve created this for loop as part of an exercise:

type Occurrences = List[(Char, Int)]

def combinations(occurrences: Occurrences): List[Occurrences] = {
  if (occurrences.isEmpty) List()
  else {
    val (chr, cnt) = occurrences.head
    val xx = for {
      count <- 1 to cnt
      item = (chr, count)
      rest <- combinations(occurrences.tail)
    } yield item :: rest
    xx.toList
  }
}

val abba = List(('a', 2), ('b', 2))
combinations(abba)

The idea is that it should return a list similar to this:

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

However, this resolves to List() :slightly_frowning_face:

I tried to add all kind of prints and it seems that it stops at the rest assignment (although it does run combinations with the tail). For some reason it doesn’t seem to complete the loop.

Can you please help?

Thanks.

#2

This loop does work however:

    occurrences match {
      case Nil => List()
      case (chr, cnt) :: Nil => {
        for {
          count <- 1 to cnt
          item = (chr, count)
        } yield List(item)
      }.toList
      case (chr, cnt) :: rest => {
        for {
          count <- 1 to cnt
          item = (chr, count)
          rr <- combinations(rest)
        } yield item :: rr
      }.toList
    }

Can someone please help me understand why?

Thanks.

#3

The problem was here. It should return List(List()) and not List(), although I’m not sure exactly why. It’s like it tried to cons element to non list and did’t do anything but also didn’t fail.

Note that this is on 2.11.

Is someone can explain the details to me I’ll appreciate it :slightly_smiling_face:.

Thanks.

#4

I feel like I’m talking to myself :smile:,

It’s just so if someone encounter this in a search, I think the reason is that the last element of the for didn’t return any results so the for loop itself didn’t return any result? does it make sense?

#5

That’s correct. A for-comprehension with multiple lines works similar to nested loops. So your last line would loop over the combinations(occurrences.tail), which for the end of the recursion will return an empty list, and therefore the loop in the recursion layer above will also be empty, and so on.
That’s why the solution which handles the last cons specially works.

When you returned List(), the for comprehension did nothing in the rest <- combinations(occurrences.tail) line. That line would then iterate over all elements of the empty list (i.e. not ever enter the loop body). With List(List()) it will iterate over a List wich contains an empty list as its only element, which means the body will be entered once with rr being the empty list.

So replacing List() with List(List()) in your first approach fixes the problem, but will of course also return List(List()) instead of List() if the original input to the function is empty, which may or may not be a problem, depending on what you want to do with it.

#6

Thanks, I spent some time after that in learning techniques to debug for loops and I figured it out. In my case List(List()) was the desired solution

Cheers.