Module Data.Queue

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: December 2018

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.