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

Question

I have a recursive function that I am trying to make @tailrec by having the inner, recursive part (countR3) add elements to a queue (agenda is a scala.collections.mutable.Queue). My idea is to then have the outer part of the function fold over the agenda and sum up the results.

NOTE: This was a homework problem, thus I don't want to post the whole code; however, making the implementation tail-recursive was not part of the homework.

Here is the portion of the code relevant 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

This almost seems to work… The problem is that it doesn't iterate over all of the items added to the agenda, yet it does process some of them. You can see this in the output below:

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'm generally well-aware of the hazards of mutating a collection while you're iterating over it in, say, Java. But a Queue is kind of a horse of a different color. Of course, I understand I could simply write an imperative loop, like so:

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

This works perfectly well, but this being Scala, I am exploring to see if there is a more functionally elegant way.

Any suggestions?

Answer 1

Although probably not entirely idiomatic, you could try this:

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

• The Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) }) gives you an infinite stream of queue items wrapped in Option[Tuple2[Int, List[Int]]].
• Then, takeWhile(_.isDefined) cuts off the sequence as soon as the first None item is encountered, i.e. when the queue is exhausted.
• As the previous call still yields a sequence of Options, we need to unwrap them with flatten.
• map({ case (x, y) => countR3(x, y) }) basically applies your function to each item.
• And finally, toList forces the evaluation of a stream (that's what we were working with) and then sum calculates the sum of list's items.

I think the problem with agenda.foldLeft (that it processes only 'some' enqueued items) is I'd guess that it takes a (probably immutable) list of currently enqueued items, and therefore isn't affected by items that were added during the calculation.