Queues in Haskell

I am steadily improving my Haskell, and in this post I will implement a First-In First-Out Queue.

Requirements

• push an element onto a queue
• pop an element from a queue
• peek at the top element from the queue
• The queue should be FIFO (First in First Out)

0.1 First approach

We can start off with the type and data signatures. Let’s start off with the simplest way to model a queue – using a list.

data Queue a = Queue [a] deriving (Show)

Now for the types of our basic operations. push needs to take an element and a Queue and push it onto it, while pop needs to return the element, and the new modified Queue.

push  :: a -> Queue a -> Queue a
pop :: Queue a -> (a, Queue a)
peek :: Queue a -> a

The simplest solution looks like this:

data Queue a = Queue [a] deriving (Show)

push :: a -> Queue a -> Queue a
push e (Queue es) = Queue (es ++ [e])

-- Precondition: Queue is not empty
pop :: Queue a -> (a, Queue a)
pop (Queue xs) = (head xs, Queue $ tail xs)

-- Precondition: Queue is not empty
peek (Queue (x:xs)) = x

While the above will work, it’s inefficient because of the use of (++), the list concatenation operator, which takes time proportional to the length of the list, meaning around push operation is \(O(n)\) and not constant time.

0.2 Using two lists for amortized constant time operation

We can achieve amortized constant time operations by using two lists (a list in Haskell works kind of like a stack – appending and popping from the front both take constant time). Here is an algorithm that models a FIFO queue using two stacks:

Keep two stacks: inbox and outbox

push : add an element to the inbox stack
pop : 
  if the outbox is empty, pop elements off inbox one by one to outbox until inbox is empty
  pop and return an element from outbox

A moment’s thought should convince you that this models a FIFO queue. The argument for constant time operation is as follows: Every element will go through at most one popping and push operation onto the outbox stack.

The implementation in Haskell:

data Queue a = Queue { 
  inbox :: [a], 
  outbox :: [a] 
} deriving (Eq, Show)

push :: a -> Queue a -> Queue a
push e (Queue inb out) = Queue (e:inb) out

pop :: Queue a -> (a, Queue a)
pop q@(Queue inb []) = pop $ Queue [] (reverse inb)
pop (Queue inb outb) = (head outb, Queue inb (tail outb))

0.3 Using Maybe

This is better, but we are still relying on preconditions that the stack is non-empty when popping. In addition, we haven’t met the requirement yet since our stack doesn’t have a peek operation. If you think about it though, the peek operation will need to have a type signature Queue a -> (a, Queue a) even though it doesn’t semantically modify the stack, but it has to internally modify it to get back the first element. This means that we then also express push in terms of peek. It looks like this:

push :: a -> Queue a -> Queue a
push e (Queue inb out) = Queue (e:inb) out

pop :: Queue a -> (Maybe a, Queue a)
pop q = 
  case top of
    Nothing   -> (top, emptyQueue)
    Just elem -> (Just elem, poppedQueue)
    where
      (top, q') = peek q
      poppedQueue = Queue (inbox q') (tail $ outbox q')

peek :: Queue a -> (Maybe a, Queue a)
peek q@(Queue [] [])    = (Nothing, emptyQueue)
peek q@(Queue inb [])   = peek $ Queue [] (reverse inb)
peek q@(Queue _ outb)   = (Just $ head outb, q)

0.4 Adding the State Monad

We can finally wrap our Queue into the State monad for easier chaining of operations.

type QueueState a = State (Queue a)

pushQueue :: a -> QueueState a ()
pushQueue e = state $ \q -> ((),push e q)

popQueue :: QueueState a (Maybe a)
popQueue = state $ \q -> pop q

Hope this was useful.