Is there an elegant way to foldLeft on a growing scala.collections.mutable.Queue?

Question

I have a recursive function that I'm trying to do @tailrec if the inner, recursive part ( countR3 ) adds items to the queue ( agenda is scala.collections.mutable.Queue ). My idea is then to move the outer part of the function above the agenda and summarize the results.

NOTE. This was a home issue, so I do not want to publish all the code; however, implementing tail recursion was not part of the homework.

Here is the piece of code related to my question:

 import scala.collection.mutable.Queue val agenda: Queue[Tuple2[Int, List[Int]]] = Queue() @tailrec def countR3(y: Int, x: List[Int]): Int = { if (y == 0) 1 else if (x.isEmpty) 0 else if … else { agenda.enqueue((y - x.head, x)) countR3(y, x.tail) } } ⋮ agenda.enqueue((4, List(1, 2))) val count = agenda.foldLeft(0) { (count, pair) => { val mohr = countR3(pair._1, pair._2) println("count=" + count + " countR3=" + mohr) count + mohr } } println(agenda.mkString(" + ")) count 

It almost seems to work ... The problem is that it does not iterate over all the items added to the agenda, but it does handle some of them. You can see it in the following figure:

 count=0 countR3=0 count=0 countR3=0 count=0 countR3=0 (4,List(1, 2)) + (3,List(1, 2)) + (2,List(2)) + (2,List(1, 2)) + (1,List(2)) + (0,List(2)) 

[Of the six items on the final agenda, only the first three were processed.]

I am generally well aware of the dangers of a collection mutation as long as you repeat it, say, in Java. But the line is a kind of horse of a different color. Of course, I understand that I can just write an imperative loop, for example:

 var count = 0 while (!agenda.isEmpty) { val pair = agenda.dequeue() count += countR3(pair._1, pair._2) } 

This works fine, but this is Scala, I am investigating if there is a more functionally elegant way.

Any suggestions?

Answer 1

Although probably not completely idiomatic, you can try the following:

 Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) }). takeWhile(_.isDefined).flatten. map({ case (x, y) => countR3(x, y) }). toList.sum 

• Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) }) provides an endless stream of queue items wrapped in Option[Tuple2[Int, List[Int]]] .
• Then, takeWhile(_.isDefined) disables the sequence as soon as the first None element is encountered, that is, when the queue is exhausted.
• Since the previous call still gives the Option s sequence, we need to deploy them using flatten .
• map({ case (x, y) => countR3(x, y) }) basically applies your function to each element.
• And finally, toList forces toList to evaluate the stream (with which we worked), and then sum calculates the sum of the list items.

I think that the problem is with agenda.foldLeft (that it only processes "some" of the objects in the queue), I would suggest that this requires a (possibly unchanged) list of items in the queue, and therefore they are not affected by the items, which were added during the calculation.