Skip to main content

Queue

Import Queue for a persistent FIFO collection. Enqueueing adds values at the rear; observation and removal use the oldest value. The representation and constructor are private. queueEmpty and queueSingleton construction, size, emptiness, and enqueue are O(1).

Type​

Queue​

Queue(a) stores values of type a. Every update returns a new queue and leaves older queue values valid.

Construction and views​

queueEmpty​

queueEmpty :: Queue(a).

queueSingleton​

queueSingleton :: a -> Queue(a).

queueFromList​

queueFromList :: [a] -> Queue(a).

Constructs a queue whose FIFO order matches the input order in O(n) time.

queueToList​

queueToList :: Queue(a) -> [a].

Returns values from oldest to newest in O(n).

queueSize​

queueSize :: Queue(a) -> Int.

queueIsEmpty​

queueIsEmpty :: Queue(a) -> Bool.

Updating and observing​

queueEnqueue​

queueEnqueue :: Queue(a) -> a -> Queue(a).

queueEnqueueAll​

queueEnqueueAll :: Queue(a) -> [a] -> Queue(a).

Adds values at the rear in list order. Enqueueing m values is O(m).

queuePeek​

queuePeek :: Queue(a) -> Maybe(a).

Returns the oldest value as Just, or Nothing for an empty queue. queuePeek is O(1) when the front is populated and O(n) when it must reverse a non-empty rear to find the oldest value. Because queuePeek does not return the normalized queue, repeated peeks of the same front-empty value repeat that O(n) work.

queueDequeue​

queueDequeue :: Queue(a) -> Maybe((a, Queue(a))).

Returns the oldest value and the remaining queue, or Nothing when empty. A single call may spend O(n) normalizing the rear. queueDequeue is amortized O(1) only across a dequeue sequence that keeps using each returned queue.

Transforming and folding​

queueMap​

queueMap :: Queue(a) -> (a -> b) -> Queue(b).

Transforms every value and preserves FIFO order in the returned queue. Callback evaluation order is not guaranteed. This is O(n) plus callback work.

queueFoldLeft​

queueFoldLeft :: Queue(a) -> b -> (b -> a -> b) -> b.

Folds from oldest to newest, beginning with the supplied accumulator. This is O(n) plus callback work.

queueFoldRight​

queueFoldRight :: Queue(a) -> b -> (a -> b -> b) -> b.

Folds from newest to oldest, beginning with the supplied terminal value. This is O(n) plus callback work.

Empty observations use Maybe.