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.

The implementation in Haskell:

## 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.

Hope this was useful.