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

functional-programming, mutable, queue, scala

Solution

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 `Option`s, 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.

Problem

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?

Original source