UU.DData.Queue

Queue type

data Queue a

Instances

Eq a => Eq (Queue a)

Show a => Show (Queue a)

Operators

(<>) :: Queue a -> Queue a -> Queue a

O(n). Append two queues, see append.

Query

isEmpty :: Queue a -> Bool

O(1). Is the queue empty?

length :: Queue a -> Int

O(n). The number of elements in the queue.

head :: Queue a -> a

O(1). The element in front of the queue. Raises an error when the queue is empty.

tail :: Queue a -> Queue a

O(1). The tail of the queue. Raises an error when the queue is empty.

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

O(1). The head and tail of the queue.

Construction

empty :: Queue a

O(1). The empty queue.

single :: a -> Queue a

O(1). A queue of one element.

insert :: a -> Queue a -> Queue a

O(1). Insert an element at the back of a queue.

append :: Queue a -> Queue a -> Queue a

O(n). Append two queues.

Filter

filter :: (a -> Bool) -> Queue a -> Queue a

O(n). Filter elements according to some predicate.

partition :: (a -> Bool) -> Queue a -> (Queue a, Queue a)

O(n). Partition the elements according to some predicate.

Fold

foldL :: (b -> a -> b) -> b -> Queue a -> b

O(n). Fold over the elements from left to right (ie. head to tail).

foldR :: (a -> b -> b) -> b -> Queue a -> b

O(n). Fold over the elements from right to left (ie. tail to head).

Conversion

elems :: Queue a -> [a]

O(n). The elements of a queue.

List

toList :: Queue a -> [a]

O(n). Convert to a list.

fromList :: [a] -> Queue a

O(n). Convert from a list.