A simple queue implementation in Haskell

Question

I'm a member of a discord channel and sometimes people post simple coding exercises for fun. This time the exercise was:

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty

Example:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

I didn't implement it using stacks because I don't know of any that are in the standard Haskell library but
I came up with this Solution:

data Queue a = Empty | Value a (Queue a) deriving (Show, Eq, Read)
push :: a -> Queue a -> Queue a
push x Empty = Value x Empty
push x (Value a pointer) = Value a (push x pointer)
pop :: Queue a -> Maybe (a, Queue a)
pop Empty = Nothing
pop (Value a pointer) = Just (a, pointer)
peek :: Queue a -> Maybe a
peek Empty = Nothing
peek (Value a _) = Just a 
empty :: Queue a -> Bool
empty Empty = True
empty _ = False

I'm currently trying to understand Haskell better and was wondering if there was a more idiomatic Solution.

• cole: This queue takes O(n) time to enqueue, unlike the common queue implementation which uses a doubly linked list. You can get an amortized O(1) time for enqueues if you implement it with two stacks (which is probably what you were getting at with the stack comment). A stack can be implemented using a singly linked list, which is what lists in haskell are. You can either make an abstract data type for a stack and use that in your queue ADT or just use lists.

Answer 1

While this is some pretty idiomatic haskell, you definitely didn't implement the challenge the way it was intended to be solved. Either way: here's some minor comments I'd want to put out anyways:

• The type-signature of pop implies, that the queue returned can basically be Nothing. If it can be, what queue did you call this on in the first place? I'd prefer the following signature:

  pop :: Queue a -> (Maybe a, Queue a)
  

  The implementation should be pretty straightforward :)

• I'd not use a for both the type-variable and the variable in all your functions. Consider explicitly differentiating between types and values:

  push x (Value value tail') = Value value (push x tail')
  pop (Value value tail') = Just (value, tail')
  peek (Value value _) = Just value
  

  This makes the differentiation more clear. Note that I've renamed pointer to tail'. One could also argue for a rename of Value to Element to make the distinction more clear as well.

  The naming changes are mostly nitpicks, though.

Now let's examine how to "correctly" solve this challenge. As cole outlines in their comment:

This queue takes \$O(n)\$ time to enqueue, unlike the common queue implementation which uses a doubly linked list. You can get an amortized \$O(1)\$ time for enqueues if you implement it with two stacks (which is probably what you were getting at with the stack comment). A stack can be implemented using a singly linked list, which is what lists in haskell are. You can either make an abstract data type for a stack and use that in your queue ADT or just use lists
_{minor formatting by me}

So how would we implement a queue using two stacks, or rather two haskell lists that take the function of stacks? The basic idea of this challenge is to realize that packing two LIFO data structures can make for a FIFO datastructure. Take an "input" stack and an "output" stack. push (or more semantically correctly push_back) will just push a value to the "input" stack.

pop (and peek) are a little more complex. They need to handle the case of an empty output stack. If the output stack is empty, the input stack is moved to the output stack using the basic LIFO operations. Note that this "reverses the order" in the stack, which explains how two LIFO datastructures turn into a FIFO datastructure.

Unfortunately this means something for the interface you've outlined there. We can't assume that peek does not modify the internal state of the Queue anymore. It's simply speaking "not idempotent" anymore, since an empty output stack requires moving the input stack to it.

Now let's look at some type definitions

type Queue a = ([a], [a]) 
push :: a -> Queue a -> Queue a
pop :: Queue a -> (Maybe a, Queue a)
peek :: Queue a -> (Maybe a, Queue a)
empty :: Queue a -> Bool

Now to implement this:

push x (input, output) = (x:input, output)
pop ([], []) = (Nothing, ([], []))
pop (input, []) = (Just val, ([], new_out))
 where (val, new_out) = fromJust $ uncons $ reverse input
pop (input, (o:os)) = (Just o, (input, os))
peek ([], []) = (Nothing, ([], []))
peek (input, []) = (Just val, ([], new_out))
 where 
 new_out = reverse input
 val = head new_out
peek (input, output@(o:_)) = (Just o, (input, output))
empty ([], []) = True
empty _ = False

For whatever it's worth: I liked your implementation better :)

Answer 2

Your data definition for the queue is just the default list in Haskell. So instead of writing

data Queue a = Empty | Value a (Queue a) deriving (Show, Eq, Read)

you could have written

data Queue a = Queue [a] deriving (Show, Eq, Read)

or

newtype Queue a = Queue [a] deriving (Show, Eq, Read)

or just

type Queue a = [a] 

• Tom Busby: This doesn't have the performance characteristic that you'd generally associate with a queue (i.e. O(1) to add an item to the queue, and the take an item from it).
• Tom Busby: Haskell lists are ideal for implementing stacks, but implementing a queue efficiently typically requires pointers, which are absent in Haskell, so some other trickery is needed.