Help with this for comprehension loop - HALF SOLVED

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 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()`

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.

Thanks.

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
}
``````

Thanks.

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 .

Thanks.

I feel like I’m talking to myself ,

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?

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.

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.

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]
}
``````

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