What is the need for an Immutable Queue?

Question

I have been working with Java for several years now. Recently came across Vavr, a functional library for Java, that provides immutable collection API. I am curious to know the reason for having an immutable Queue.

My understanding is that a Queue is used to produce data to it on one end and then a different thread consumes the data from the other end.

Immutable Queue doesn`t allow you to add data after its construction, then why would I use a Queue here.

Ideally, I would process a Queue as below, but for an immutable Queue, this goes into an infinite loop.

while(!queue.isEmpty()) {
    queue.dequeue(); // process elements in queue.
}

When I googled, all of the discussions are around how to implement an immutable queue, but doesn't explain the need for it.

Answer 1

My understanding is that a Queue is used to produce data to it on one end and then a different thread consumes the data from the other end.

A Queue is a FIFO (First-In-First-Out) data structure. It has many uses, other than as communication between threads.

I am curious to know the reason for having an immutable Queue.

If you are baffled by the need for an immutable anything, it seems that you don't understand functional programming. Remember, you said yourself that Vavr is a functional library, i.e. a library for writing functional code in Java.

One of the basic principles of functional programming is that everything is immutable.

This includes a Queue. If you need a queue, i.e. a FIFO collection, for storing your data, then it has to be immutable too.

As an example, let's say you wanted to add the numbers 1 to 10 to a queue, and then read from that queue and print the values.

In an imperative programming language like Java, you'd do that like this, using java.util.Queue and an implementation such as java.util.LinkedList:

// Build queue with numbers 1-10
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= 10; i++)
    queue.offer(i);

// Poll queue and print numbers
for (Integer num; (num = queue.poll()) != null; )
    System.out.println(num);

In contrast, functional programming relies heavily on recursive functions (hence functional programming), for operations like that, where nested call invocation on the stack has different values for the functions parameters.

Remember, in the imperative style, the counting variable i and the queue queue are both mutated during iteration.

In the functional style, they must both be immutable, so you do it by writing a recursive function like this (in Java), using io.vavr.collection.Queue:

private static Queue<Integer> build(int i, int end, Queue<Integer> queue) {
    if (i > end)
        return queue;
    return build(i + 1, end, queue.enqueue(i));
}

Then call it:

// Build queue with numbers 1-10
Queue<Integer> queue = build(1, 10, Queue.empty());

Since the queue is immutable, the enqueue() method returns a new queue with the new value added. That new queue is then passed as parameter on the recursive call, until done, at which point the final queue containing the numbers are returned back up the call stack.

Side-note: In a functional language, that implements tail-recursion optimization (Java doesn't), the build() function above will not actually build up a call stack, so it won't cause a stack overflow. Also, the new queue returned by enqueue() does not copy all existing values, so it's not as expensive as it sounds.

To then poll the values from the queue and print them, you'd also use a recursive method:

private static void print(Queue<Integer> queue) {
    if (queue.isEmpty())
        return;
    Tuple2<Integer,Queue<Integer>> t = queue.dequeue();
    System.out.println(t._1());
    print(t._2());
}

Here, dequeue() returns two values: the value removed from the queue, and the new queue with the value removed. The function then prints the value and makes a recursive call to print the rest of the queue.