#### Posted on November 20, 2013

##### Last updated on November 22, 2013

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.

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.

The simplest solution looks like this:

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:

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.

## 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:
## 0.4 Adding the State Monad
We can finally wrap our Queue into the State monad for easier chaining of operations.