Help with this for comprehension loop - HALF SOLVED

Question
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.

7

This is resolved but I wanted to mention normally you do not provide further looping on the tail inside the for loop. Rather you do the needed work on head then cons that work onto the recursive work on the tail. Doing it that way avoids the situation you bumped into.

def combinations(occurrences: Occurances): List[Occurances] =
  if (occurences.isEmpty)
    List.empty[Occurences]
  else {
    val (chr, cnt) :: rest  = occurences // pattern match to get all the parts
    val newhead = (1 to cnt).map{n => (chr, n)}.toList // a single Occurences
    newhead :: combinations(rest) // which we cons onto a List[Occurences]
  }
8

Great, thanks for the tip. I’ll try it out when I’m back form vacation :smile:.