This is actually not too difficult (and an interesting exercise) to flip your own FIFO queue in Haskell. I can appreciate that you want to use the standard model for this, and that is almost certainly what you should do. But I just found out about it last week, and I'm too excited to not write about it.
Here is a simple queue class that allows you to check if it is empty, get the first element from the head of the queue (and return the rest of the queue) and insert a new element into the queue.
class Queue q where empty :: qa -> Bool get :: qa -> (a, qa) ins :: a -> qa -> qa
The easiest way to make a FIFO queue is to use 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 terribly inefficient. If there are n elements in the queue, then inserting a new element takes O (n). If you want to insert m elements into an empty queue, this will take O (m 2 ) time. Can we make a queue that inserts and retrieves elements O (1) times (or at least O (1) amortized time)?
The trick is to store the front and back of the queue in separate lists, and the back of the queue is stored in the reverse order:
data Fifo a = F [a] [a] instance Queue Fifo where
The queue is empty if the front and back are empty:
empty (F xs ys) = null xs && null ys
To insert a new item into the list, we simply transfer it to the reverse queue, which takes O (1) time.
ins y (F xs ys) = F xs (y:ys)
Getting an item from the front of the queue is easy when the elements are 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 in the front of the queue, we discard the back of the queue and put it in front. Although this takes O (n) time, we need to do this only once for each element, so our get operation averages the O (1) time:
get (F [] ys) = get (F (reverse ys) [])
There you have it - O (1) FIFO queues in the functional language are amortized.
Edit:. Efie asked about the depreciated performance of O (1) in the comments. The argument for amortized constant time is pretty simple.
Consider a sequence of n inserts in an empty queue, followed by n retrievals. Insertions take time n. At the first search, the front of the queue is empty, so we need to cancel the reverse queue of the queue, which also takes time n, plus 1 to retrieve the item. finally, the next n-1 extracts take time 1 each, so the total time
n + n + 1 + n - 1 = 3 n
In total, 2 n calls were made, so the amortized time is 3 n / 2 n = 3/2, which is O (1). The same argument works regardless of how the calls ins and get alternate - in two calls, each element once once, once moved and de-cons -ed once.