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. empty and singleton 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
empty
singleton
fromList
Constructs a queue whose FIFO order matches the input order in O(n) time.
toList
Returns values from oldest to newest in O(n).
size
isEmpty
Updating and observing
enqueue
enqueueAll
Adds values at the rear in list order. Enqueueing m values is O(m).
peek
Returns the oldest value as Just, or Nothing for an empty queue.
peek 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 peek does not
return the normalized queue, repeated peeks of the same front-empty value repeat
that O(n) work.
dequeue
Returns the oldest value and the remaining queue, or Nothing when empty. A
single call may spend O(n) normalizing the rear. dequeue is amortized
O(1) only across a dequeue sequence that keeps using each returned queue.
Transforming and folding
map
Transforms every value and preserves FIFO order in the returned queue. Callback
evaluation order is not guaranteed. This is O(n) plus callback work.
foldLeft
Folds from oldest to newest, beginning with the supplied accumulator. This is
O(n) plus callback work.
foldRight
Folds from newest to oldest, beginning with the supplied terminal value. This
is O(n) plus callback work.
Empty observations use Maybe.
Generic methods
Importing Queue supplies element-based Equatable, Mappable, Reducible, and Combinable instances.
Generic map preserves FIFO output order without guaranteeing callback evaluation order.
Generic folds follow the same oldest-to-newest or newest-to-oldest order as the corresponding Queue functions.
Equality compares FIFO contents independently of construction history.