Module Dequeue

An implementation of double-ended queues supporting access at both ends in constant amortized time.

Author: Bernd Brassel, Olaf Chitil, Michael Hanus, Sebastian Fischer, Bjoern Peemoeller

Version: January 2015

Summary of exported operations:

 ```empty :: Queue a```    The empty queue. ```cons :: a -> Queue a -> Queue a```    Inserts an element at the front of the queue. ```snoc :: a -> Queue a -> Queue a```    Inserts an element at the end of the queue. ```isEmpty :: Queue a -> Bool```    Is the queue empty? ```deqLength :: Queue a -> Int```    Returns the number of elements in the queue. ```deqHead :: Queue a -> a```    The first element of the queue. ```deqTail :: Queue a -> Queue a```    Removes an element at the front of the queue. ```deqLast :: Queue a -> a```    The last element of the queue. ```deqInit :: Queue a -> Queue a```    Removes an element at the end of the queue. ```deqReverse :: Queue a -> Queue a```    Reverses a double ended queue. ```rotate :: Queue a -> Queue a```    Moves the first element to the end of the queue. ```matchHead :: Queue a -> Maybe (a,Queue a)```    Matches the front of a queue. ```matchLast :: Queue a -> Maybe (a,Queue a)```    Matches the end of a queue. ```listToDeq :: [a] -> Queue a```    Transforms a list to a double ended queue. ```deqToList :: Queue a -> [a]```    Transforms a double ended queue to a list.

Exported datatypes:

Queue

The datatype of a queue.

Constructors:

Exported operations:

 ```empty :: Queue a```    The empty queue. Further infos: solution complete, i.e., able to compute all solutions
 ```cons :: a -> Queue a -> Queue a```    Inserts an element at the front of the queue.
 ```snoc :: a -> Queue a -> Queue a```    Inserts an element at the end of the queue.
 ```isEmpty :: Queue a -> Bool```    Is the queue empty?
 ```deqLength :: Queue a -> Int```    Returns the number of elements in the queue.
 ```deqHead :: Queue a -> a```    The first element of the queue.
 ```deqTail :: Queue a -> Queue a```    Removes an element at the front of the queue.
 ```deqLast :: Queue a -> a```    The last element of the queue.
 ```deqInit :: Queue a -> Queue a```    Removes an element at the end of the queue.
 ```deqReverse :: Queue a -> Queue a```    Reverses a double ended queue. Further infos: solution complete, i.e., able to compute all solutions
 ```rotate :: Queue a -> Queue a```    Moves the first element to the end of the queue.
 ```matchHead :: Queue a -> Maybe (a,Queue a)```    Matches the front of a queue. `matchHead q` is equivalent to `if isEmpty q then Nothing else Just (deqHead q, deqTail q)` but more efficient.
 ```matchLast :: Queue a -> Maybe (a,Queue a)```    Matches the end of a queue. `matchLast q` is equivalent to `if isEmpty q then Nothing else Just (deqLast q,deqInit q)` but more efficient.
 ```listToDeq :: [a] -> Queue a```    Transforms a list to a double ended queue.
 ```deqToList :: Queue a -> [a]```    Transforms a double ended queue to a list.