Haskell - Queue (1) P80618

We want to represent queues to improve the efficiency of its push and pop operations. In order to do so, we implement queues through two lists, so that if we concatenate the first with the reverse of the second, we get the elements of the queue if exit order. Using a Queue constructor for this type,

q = Queue [2,8,5] [4,7]

would represent que queue where the first element is 2, followed by 8, 5, 7 and 4.

In this way, the push operation is made by prepending an element to the second list (which is less expensive than appending it to its end).

On the other hand, the pop operation is now made by extracting the first element in the first queue, provided it exists. If it does not exist, all the elements in the second list are transferred to the first list (by reversing its order).

1. Implement generic queues using the following interface:

   data Queue a = Queue [a] [a]
       deriving (Show)
   
   create :: Queue a
   push :: a -> Queue a -> Queue a
   pop :: Queue a -> Queue a
   top :: Queue a -> a
   empty :: Queue a -> Bool

2. Define equality for queues so that two queues are equal if and only if they have the same elements, in the same order, independently of their representation. In order to do so, write that queues are an instance of the Eq class, where (==) is the equality operation you have to define:

   instance Eq a => Eq (Queue a)
       where
           ...

   Observe that, in order to have Queue a be an instance of Eq, it is necessary to have that the elements of type a are them-selves also instances of Eq.

Scoring

Each section scores 50 points.