Haskell type class for Queue

Question

Has anyone written a Haskell type class (or is there a combination of type classes) that describes a FIFO queue.

Data.Collection.Sequence seems too strong, but on the other hand Data.Collection.Unfoldable seems too weak (as order is not defined).

I just wanted to not redo someone else's work.

Answer 1

It's actually not too hard (and an interesting exercise) to roll your own FIFO queue in Haskell. I can appreciate your wanting to use a standard typeclass for this, and that's almost certainly what you should do. But I just learnt about this last week, and I'm too excited not to write about it.

Here's a simple queue class, that allows you to check whether the queue is empty, to get the first element from the head of the queue (and return the rest of the queue) and to insert a new element into the queue.

class Queue q where
  empty :: q a -> Bool
  get :: q a -> (a, q a)
  ins :: a -> q a -> q a

The simplest way to make a FIFO queue is using a list:

instance Queue [] where
  empty = null

  get []     = error "Can't retrieve elements from an empty list"
  get (x:xs) = (x, xs)

  ins x xs = xs ++ [x]

However, this is horribly inefficient. If the queue currently has n elements, then inserting a new element takes O(n) time. If you want to insert m elements into an empty queue, that takes O(m²) time. Can we make a queue that inserts and retrieves elements in O(1) time (or at the least, O(1) amortized time)?

The trick is to store the front and back of the queue in separate lists, with the back of the queue being stored in reverse:

data Fifo a = F [a] [a]

instance Queue Fifo where

The queue is empty if both the front and the back are empty:

  empty (F xs ys) = null xs && null ys

To insert a new element into the list, we just cons it onto the back queue, which takes O(1) time.

  ins y (F xs ys) = F xs (y:ys)

Getting an element from the front of the queue is easy when there are elements waiting there (and we throw an error if the queue is empty)

  get (F []     []) = error "Can't retrieve elements from an empty queue"
  get (F (x:xs) ys) = (x, F xs ys)

Finally, if there are no elements waiting at the front of the queue, then we reverse the back of the queue and put it at the front. Although this takes O(n) time, we only have to do it once for each element, so our get operation averages out to O(1) time:

  get (F [] ys) = get (F (reverse ys) [])

There you have it - amortized O(1) FIFO queues in a functional language.

---

Edit: Efie asked about the amortized O(1) performance in the comments. The argument for amortized constant time is pretty simple.

Consider a sequence of n insertions to an empty queue, followed by n retrievals. The insertions take time n. On the first retrieval, the front of the queue is empty, so we have to reverse the back of the queue, which also takes time n, plus 1 to retrieve the element. finally, the next n - 1 retrievals take time 1 each, so the total time is

n + n + 1 + n - 1 = 3 n

We made 2 n calls in total, so the amortized time is 3 n / 2 n = 3/2, which is O(1). The same argument works no matter how the calls to ins and get are interleaved - in two calls, each element is cons'ed once, moved once and de-cons'ed once.