26

I have what I would think is the most common case for processing a queue. I will read off the front of the queue, act on the element (which may cause more elements to be added to the queue), and then loop until the queue is empty.

  1. My first instinct was foreach, but no, apparently a queue (even a mutable one) is strict and the foreach loops over all the elements that are in the queue when the iteration starts.
  2. I cannot figure out the syntax for a while loop.

You'd think that it would be something like

while (!q.isEmpty) {
   var (e, q) = q.dequeue
   ... }

would work, except that I'm redeclaring q. This does work:

while (!q.isEmpty) {
   var (e, q1) = q.dequeue
   q = q1
   ... }

but man, does it look wrong ...

Michael Lorton
  • 43,060
  • 26
  • 103
  • 144

3 Answers3

17

Here's one way to avoid any vars at all:

val q0 = collection.immutable.Queue("1","Two","iii")
Iterator.iterate(q0) { qi =>
  val (e,q) = qi.dequeue
  println("I just dequeued "+e)  // Your side-effecting operations go here
  if (e.length!=2) q.enqueue("..")  // Your changes to the queue go here
  else q
}.takeWhile(! _.isEmpty).foreach(identity)

You start with the initial queue, q0, and then on the qith step, you dequeue something and produce a new queue if need be, returning that for the next step.

All you have left is the stopping condition (not empty), and then since this just defines a process, not the actual action, you have to run it (using a no-op foreach, for example).

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • Now *that's* good. I haven't tried it, but it's what I had in mind. Actually, the additions to the queue are being done deep in the call tree of the side-effecting operations so I may have to make a temporary holding area available, but I think it will work. – Michael Lorton Dec 27 '10 at 22:38
14

While Rex Kerr's answer is good, iterators are mutable. Here's a truly immutable solution, modeled very closely on the code in Rex Kerr's own answer.

val q0 = collection.immutable.Queue("1","Two","iii")
@annotation.tailrec def processQueue(queue: collection.immutable.Queue[String]): Unit = if (queue.nonEmpty) {
    val (element, rest) = queue.dequeue
    println("I just dequeued "+element)
    if (element.length != 2) processQueue(rest.enqueue(".."))
    else processQueue(rest)
}
processQueue(q0)
Community
  • 1
  • 1
Daniel C. Sobral
  • 295,120
  • 86
  • 501
  • 681
  • Tail-recursive code is mutable internally; you're just protected from it. Given that the iterator pattern, used as I did, also protects you from mutable internals, I don't see the distinction in this case. (Though I do think it is valuable to know how to use tail recursion as well; it's just often got more awkward syntax for these sorts of problems.) – Rex Kerr Dec 28 '10 at 16:55
  • 2
    @Rex Kerr Every code is mutable internally, because all real processors we use cannot do a single thing without mutability, so that argument is absolutely bollocks. It's a compiler-side optimization that does not concern the programmer. – Daniel C. Sobral Dec 28 '10 at 19:24
  • 7
    If I gain nothing else from this question and the various responses, it's the expression "that argument is absolutely bollocks", which I intend to use at the very next opportunity and frequently thereafter. – Michael Lorton Dec 28 '10 at 20:13
  • 2
    For those who, like me, wondered where the term _bollocks_ came from and what it means: http://en.wikipedia.org/wiki/Bollocks. Very interesting that it has come to mean _nonsense_. – Aaron Novstrup Dec 28 '10 at 22:49
  • @Daniel - I think we're making the same point. I have nothing against tail recursion (and certainly not against its internal use of mutable state)! But where in the pattern that I used need the programmer be concerned about mutability? – Rex Kerr Dec 29 '10 at 03:59
  • @Rex Well... when you put it that way, no where. It's just the principle of the thing. :-) – Daniel C. Sobral Dec 29 '10 at 10:36
9

Processing a Queue in a while loop can be done without a duplicate var/val as follows:

var q = Queue("foo", "bar", "baz")
while (q.nonEmpty) {
  val e = q.head
  q = q.tail
  // Do something with `e` here
}

(I am aware that this answer is 7 years late, but I thought it a valuable alternative nonetheless.)

NthPortal
  • 372
  • 5
  • 7
  • Is it too dirty to do something like: `a.foreach(processElement); q = Queue.empty[String]`? – Onema Mar 29 '19 at 03:14
  • Six years later — yes, it is too “dirty”. It is predicated on a _variable_ (an actually varying variable, not just a named constant) which is anathema to functional programming. – Michael Lorton Jul 10 '23 at 17:56