Introduction

A queue needs fast insertion at the back and fast removal from the front, which makes a plain Haskell list a poor fit for general FIFO workloads. The usual functional solution is a two-list queue that keeps one list for the front and another list for recently added items, giving amortized constant-time operations.

Why a Single List Is Not Enough

A Haskell list is excellent for adding or removing at the head with (:) and pattern matching. It is not efficient for appending at the end.

A naive queue might look like this:

1enqueue :: a -> [a] -> [a]
2enqueue x xs = xs ++ [x]
3
4dequeue :: [a] -> Maybe (a, [a])
5dequeue []     = Nothing
6dequeue (x:xs) = Just (x, xs)

dequeue is cheap, but enqueue is O(n) because ++ must walk the whole list. For queue-heavy code that cost adds up quickly.

The Two-List Queue

A better representation stores the front of the queue in one list and the rear in reverse order in another list.

1data Queue a = Queue [a] [a]
2  deriving (Show)
3
4empty :: Queue a
5empty = Queue [] []

When the front list becomes empty, reverse the rear list and use that as the new front.

1normalize :: Queue a -> Queue a
2normalize (Queue [] rear) = Queue (reverse rear) []
3normalize q               = q
4
5enqueue :: a -> Queue a -> Queue a
6enqueue x (Queue front rear) = normalize (Queue front (x : rear))
7
8dequeue :: Queue a -> Maybe (a, Queue a)
9dequeue (Queue [] [])     = Nothing
10dequeue (Queue (x:xs) r)  = Just (x, normalize (Queue xs r))
11dequeue (Queue [] r)      = dequeue (normalize (Queue [] r))

Example use:

1main :: IO ()
2main = do
3  let q0 = empty
4      q1 = enqueue 1 q0
5      q2 = enqueue 2 q1
6      q3 = enqueue 3 q2
7  print q3
8  print (dequeue q3)

The rear list is built with (:), which is cheap, and reversed only occasionally.

Why the Complexity Is Amortized O(1)

Reversing the rear list costs O(n), so at first glance the queue may not look constant time. The important point is that each element moves from the rear list to the front list at most once before being removed.

That means the expensive reversal work is spread across many enqueue and dequeue operations. Over a long sequence of operations, the average cost per operation is constant. This is the standard amortized analysis for a persistent queue.

A More Complete API

A practical queue often includes peek and isEmpty.

1peek :: Queue a -> Maybe a
2peek q = case normalize q of
3  Queue [] _    -> Nothing
4  Queue (x:_) _ -> Just x
5
6isEmpty :: Queue a -> Bool
7isEmpty (Queue [] []) = True
8isEmpty _             = False

Keeping normalize as a small helper makes the rest of the API easy to reason about.

Library Option: Data.Sequence

If you need a production-ready general-purpose queue, Data.Sequence is often an even better choice than writing your own. It provides efficient access at both ends and is already well tested.

1import qualified Data.Sequence as Seq
2import Data.Sequence (Seq((:<|)), (|>))
3
4let q0 = Seq.empty
5let q1 = q0 |> 1 |> 2 |> 3
6case q1 of
7  x :<| rest -> print (x, rest)
8  _          -> putStrLn "empty"

This is especially appealing when the queue is only one part of a larger program and you do not want to maintain a custom data structure.

Common Pitfalls

The most common mistake is using xs ++ [x] for every enqueue. It works, but the performance is linear per insert.

Another issue is forgetting to normalize after the front list becomes empty. Without that step, dequeues can fail even though elements are waiting in the rear list.

It is also easy to overengineer the queue too early. If the application already depends on containers, Data.Sequence may be the better answer.

Finally, remember that amortized O(1) does not mean every single operation is constant time. Occasional reversals still happen, but the average remains efficient.

Summary

• A plain list makes queue insertion at the back too expensive.
• A two-list queue gives amortized O(1) enqueue and dequeue.
• 'normalize is the key helper that moves reversed rear elements to the front.'
• Use Data.Sequence when you want a tested library implementation.
• Think in amortized cost, not worst-case cost of one operation.